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 subarraysvoid 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 Codeint 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 subarraysimport 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 codepublic 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 Codearr = [ 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 subarraysfunction 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 Codevar arr = [1, 2, 4, 3, 6, 5];var N = 6;countbitonic(arr, N);// This code is contributed by rutvik_56.</script> |
Output:
15
Time Complexity: O (N 3)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More on that Topic: geeksforgeeks.org/count-of-all-possible-bitonic-subarrays/ […]