Count of all possible bitonic subarrays

0 0 5 minutes read

Given an array arr[] consisting of N integers, the task is to count all the subarrays which are Bitonic in nature.

A bitonic subarray is a subarray in which elements are either strictly increasing or strictly decreasing, or are first increasing and then decreasing.

Examples:

Input: arr[] = {2, 1, 4, 5}
Output: 8
Explanation:
All subarray which are bitonic in subarray are : {2}, {2, 1}, {1}, {1, 4}, {1, 4, 5}, {4}, {4, 5} and {5}.
Input: arr[] = {1, 2, 3, 4}
Output:10

Approach:
Follow the steps below to solve the problems:

Generate all possible subarrays.
For each subarray, check if it is bitonic or not. If the subarray is Bitonic then increment count for answer.
Finally return the answer.

Below is the implementation of the above approach :

C++

// C++ program to count the
// number of possible
// bitonic subarrays
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count
// of bitonic subarrays
void countbitonic(int arr[], int n)
{
    int c = 0;
    // Starting element of subarray
    for (int i = 0; i < n; i++) {
        // Ending element of subarray
        for (int j = i; j < n; j++) {
 
            int temp = arr[i], f = 0;
 
            // for 1 length
            if (j == i) {
                c++;
                continue;
            }
 
            int k = i + 1;
 
            // For increasing sequence
            while (temp < arr[k] && k <= j) {
                temp = arr[k];
                k++;
            }
 
            // If strictly increasing
            if (k > j) {
                c++;
                f = 2;
            }
 
            // For decreasing sequence
            while (temp > arr[k]
                   && k <= j
                   && f != 2) {
                temp = arr[k];
                k++;
            }
 
            if (k > j && f != 2) {
                c++;
                f = 0;
            }
        }
    }
 
    cout << c << endl;
}
// Driver Code
int main()
{
    int arr[] = { 1, 2, 4, 3, 6, 5 };
    int N = 6;
 
    countbitonic(arr, N);
}

Java

// Java program to count the number 
// of possible bitonic subarrays
import java.io.*; 
import java.util.*; 
 
class GFG{ 
     
// Function to return the count 
// of bitonic subarrays 
public static void countbitonic(int arr[], int n)
{
    int c = 0;
     
    // Starting element of subarray
    for(int i = 0; i < n; i++) 
    {
         
       // Ending element of subarray
       for(int j = i; j < n; j++) 
       {
          int temp = arr[i], f = 0;
           
          // For 1 length
          if (j == i)
          {
              c++;
              continue;
          }
          int k = i + 1;
           
          // For increasing sequence
          while (temp < arr[k] && k <= j)
          {
              temp = arr[k];
              k++;
          }
           
          // If strictly increasing
          if (k > j) 
          {
              c++;
              f = 2;
          }
           
          // For decreasing sequence
          while ( k <= j && temp > arr[k] && f != 2) 
          {
              temp = arr[k];
              k++;
          }
          if (k > j && f != 2)
          {
              c++;
              f = 0;
          }
       }
    }
    System.out.println(c);
}
 
// Driver code
public static void main(String[] args) 
{ 
    int arr[] = { 1, 2, 4, 3, 6, 5 };
    int N = 6;
     
    countbitonic(arr, N);
} 
} 
 
// This code is contributed by grand_master

Python3

# Python3 program to count the number 
# of possible bitonic subarrays
 
# Function to return the count 
# of bitonic subarrays 
def countbitonic(arr, n):
 
    c = 0;
     
    # Starting element of subarray
    for i in range(n):
         
        # Ending element of subarray
        for j in range(i, n): 
            temp = arr[i]
            f = 0;
 
            # For 1 length
            if (j == i) :
                c += 1
                continue;
            k = i + 1;
 
            # For increasing sequence
            while (temp < arr[k] and k <= j):
                temp = arr[k];
                k += 1
                 
            # If strictly increasing
            if (k > j) :
                c += 1
                f = 2;
                 
            # For decreasing sequence
            while (k <= j and temp > arr[k] and f != 2):
                temp = arr[k];
                k += 1;
                 
            if (k > j and f != 2):
                c += 1;
                f = 0;            
    print(c)
     
# Driver Code
arr = [ 1, 2, 4, 3, 6, 5 ];
N = 6;
 
countbitonic(arr, N);
 
# This code is contributed by grand_master

C#

// C# program to count the number 
// of possible bitonic subarrays 
using System;
 
class GFG{ 
 
// Function to return the count 
// of bitonic subarrays     
public static void countbitonic(int []arr, int n)
{
    int c = 0;
     
    // Starting element of subarray
    for(int i = 0; i < n; i++) 
    {
         
       // Ending element of subarray
       for(int j = i; j < n; j++)
       {
          int temp = arr[i], f = 0;
           
          // for 1 length
          if (j == i)
          {
              c++;
              continue;
          }
          int k = i + 1;
           
          // For increasing sequence
          while (temp < arr[k] && k <= j)
          {
              temp = arr[k];
              k++;
          }
           
          // If strictly increasing
          if (k > j)
          {
              c++;
              f = 2;
          }
           
          // For decreasing sequence
          while ( k <= j && temp > arr[k] && f != 2)
          {
              temp = arr[k];
              k++;
          }
          if (k > j && f != 2)
          {
              c++;
              f = 0;
          } 
       }
    }
    Console.Write(c);
}
 
// Driver code 
public static void Main() 
{ 
    int[] arr = { 1, 2, 4, 3, 6, 5 };
    int N = 6;
     
    countbitonic(arr, N);
} 
} 
 
// This code is contributed by grand_master

Javascript

<script>
 
// Javascript program to count the
// number of possible
// bitonic subarrays
 
// Function to return the count
// of bitonic subarrays
function countbitonic(arr, n)
{
    var c = 0;
     
    // Starting element of subarray
    for (var i = 0; i < n; i++) 
    {
     
        // Ending element of subarray
        for (var j = i; j < n; j++)
        {
 
            var temp = arr[i], f = 0;
 
            // for 1 length
            if (j == i)
            {
                c++;
                continue;
            }
 
            var k = i + 1;
 
            // For increasing sequence
            while (temp < arr[k] && k <= j) {
                temp = arr[k];
                k++;
            }
 
            // If strictly increasing
            if (k > j) {
                c++;
                f = 2;
            }
 
            // For decreasing sequence
            while (temp > arr[k]
                   && k <= j
                   && f != 2) {
                temp = arr[k];
                k++;
            }
 
            if (k > j && f != 2) {
                c++;
                f = 0;
            }
        }
    }
 
    document.write( c );
}
 
// Driver Code
var arr = [1, 2, 4, 3, 6, 5];
var N = 6;
countbitonic(arr, N);
 
// This code is contributed by rutvik_56.
</script>

Output:

Time Complexity: O (N³)
Auxiliary Space: O (1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!