C++ Program To Calculate The Bitonicity Of An Array

In this article, we will discuss a C++ program to calculate the Bitonicity of an Array.

The Bitonicity of an array is -

• ✅ Initialized to 0
• ✅ Incremented to one if the subsequent element is more than the previous value.
• ✅ Decremented to 1 if the following element is lesser than the preceding value.

Example:

Example
Copy
Input-: arr[] = { 1,5,4,6,3,10,11,12}
Output-: The Bitonicity of an array is : 3
Try it Yourself
• ✅ Initialize the bitonicity calculation variable's initial value to 0, let's assume temp .
• ✅ Begin with element 1, the first entry in an array. Examine arr[i] and arr[i-1] . Here, compare 5 and 1. As 5 is larger than 1, the temp is increased by 1. In the same way, compare 5 to 4; as 4 is less than 5, the temp is decreased by 1.
• ✅ Print the temp final value, which is 3.

An approach to find the bitonicity of an array:

• ✅ Go through each element in an array, let's say arr[n] , where n is the array's size.
• ✅ if arr[i] > arr[i-1] , bitonicity = bitonicity + 1
• ✅ if arr[i] < arr[i-1], bitonicity = bitonicity - 1
• ✅ In the case, when arr[i] = arr[i-1], bitonicity remains constant.

Algorithm:

Example
Copy
Start
Step 1-> In step 1, we declare cal_bitonicity function to calculate the bitonicity
   int cal_bitonicity(int arr[], int n)
      set int temp = 0
      Loop For int i = 1 and i < n and i++
         IF (arr[i] > arr[i - 1])
         Increment temp++
      End
      Else IF (arr[i] < arr[i - 1])
         Decrement temp-
      End
   return temp
step 2-> In main()
   declare int arr[] = { 1,4,5,7,3,15,10,12}
   set int n = sizeof(arr) / sizeof(arr[0])
   Call cal_bitonicity(arr, n)
Stop
Try it Yourself

Program:

Let us take an example to calculate the Bitnocity of an array in C++

#include <iostream>
using namespace std;
int findBitonicity(int arr[], int n)
{
	int bt = 0;
	for (int i = 1; i < n; i++) {
		if (arr[i] > arr[i - 1])
			bt++;
		else if (arr[i] < arr[i - 1])
			bt--;
	}
	return bt;
}
// Driver Code
int main()
{
	int arr[] = { 1, 7, 8, 4, 5, 8, 4, 3 };
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << "Bitonicity = " << findBitonicity(arr, n);
	return 0;
}

Output:

Complexity Analysis:

Time Complexity: O(N), since the bitonicity of the array is found by traversing it N times through a loop.

Space Complexity: O(1), Since no additional space complexity is being used.