What is a bitonic sequence?

Bitonic sequence

A bitonic sequence is a sequence of numbers in which, at first, the numbers are in increasing order, and after a certain point, they start decreasing.

Example

The sequence [1,3,5,7,5,3,1][1, 3, 5, 7, 5, 3, 1] is a bitonic sequence as the sequence first increases to 7 and then decreases to 1.

Types of bitonic sequences

A bitonic subsequence can be of the following three types:

  • It can consist of numbers that are first increasing and then decreasing. For example, (2,6,9,3,2)(2,6,9,3,2).

  • It can consist of numbers that are only increasing (where the decreasing part at the end is empty). For example, (2,3,7,9)(2,3,7,9).

  • It can consist of numbers that are only decreasing (where the increasing part at the start is empty). For example, (15,12,5,3,2,1)(15,12,5,3,2,1).

Example

Let's implement the code to find if the given sequence is a bitonic sequence.

#include <iostream>
using namespace std;
// Helper function to print sequence
void printSequence(int arr[], int n){
string out = "[";
for (int i = 0; i < n; i++){
out+= to_string(arr[i]) + ", ";
}
out = out.substr(0, out.length() -2);
out += "]";
cout << out << endl;
}
// Finding index of maximum value in an array
int find_maxIndex(int arr[], int n){
int max_index = 0;
for (int i = 1; i < n; i++){
if (arr[i] > arr[max_index]){
max_index = i;
}
}
return max_index;
}
bool isIncreasingBitonic(int arr[], int low, int high){
//Base case
if (high == low){
return true;
}
// Checking for the non increasing pair in array
if (arr[high] < arr[high - 1]){
return false;
}
return isIncreasingBitonic(arr, low, high - 1);
}
bool isDecreasingBitonic(int arr[], int low, int high){
// Base case
if (high == low){
return true;
}
// Checking for the non decreasing in array
if (arr[high] > arr[high - 1]){
return false;
}
return isDecreasingBitonic(arr, low, high - 1);
}
bool isBitonic(int arr[], int n, int max_index){
// If array is the increasing bitonic
// then the maximum element will be at the last index
if(max_index == n){
return isIncreasingBitonic(arr,0,n);
}
// If array is the decreasing bitonic
// then the maximum element will be at the 0th index
else if(max_index == 0){
return isDecreasingBitonic(arr,0,n);
}
// If array is first increasing and then decreasing bitonic
// First check for increasing bitonic till max value
// Then check for decreasing bitonic from max value till end of array
else{
return isIncreasingBitonic(arr,0,max_index) && isDecreasingBitonic(arr,max_index,n);
}
}
int main(){
int arr[] = {2, 3, 7, 9, 15, 10, 4};
int n = sizeof(arr) / sizeof(arr[0]);
// Finding index for maximum element
int max_index = find_maxIndex(arr,n);
//Printing sequence
cout << "The sequence is: ";
printSequence(arr, n);
// Checking if the array is bitonic
if (isBitonic(arr, n-1, max_index)){
cout << "This is a bitonic sequence." << endl;
}
else{
cout << "This is not a bitonic sequence." << endl;
}
return 0;
}

Explanation

  • Lines 5–14: We defined the printSequence() method to print the sequence.

  • Lines 17–26: We defined the find_maxIndex() method to find the index of the maximum value in the sequence.

  • Lines 28–40: We defined the recursive method isIncreasingBitonic() to find if the array is an increasing bitonic sequence.

  • Lines 42–54: We defined the recursive method isDecreasingBitonic() to find if the array is a decreasing bitonic sequence.

  • Lines 56–73: We write the isBitonic() method which uses the isIncreasingBitonic() and isDecreasingBitonic() method to find if the given sequence is a bitonic sequence or not.

Copyright ©2024 Educative, Inc. All rights reserved