Given an array arr[] of N integers, the task is to count the total number of Reverse Bitonic Subarray from the given array.
A Reverse Bitonic Subarray is a subarray in which elements are arranged in decreasing order and then arranged in increasing order. A strictly increasing or strictly decreasing subarray is also considered as Reverse Bitonic Subarray.
Examples:
Input: arr[] = {2, 3, 1, 4}
Output: 8
Explanation:
Here we will look for all length’s subarrays of given array
For length 1, all the subarrays are reverse bitonic subarray {2}, {3}, {1}, {4}
For length 2, possible subarrays are {2, 3}, {3, 1}, {1, 4}
For length 3, possible subarray is {3, 1, 4}
So in total, there are 8 subarrays possible.
Input: arr[] = [1, 2, 3]
Output: 6
Explanation:
Here we will look for all length’s subarrays of given array
For length 1, all the subarrays are reverse bitonic {1}, {2}, {3}
For length 2, possible subarrays are {1, 2}, {2, 3}
For length 3, possible subarray is {1, 2, 3}.
So in total, there are 6 subarrays possible.
Approach: The idea is to generate all the subarrays from the given array and check if each subarray satisfy the below mentioned conditions:
- When the subarray elements are strictly increasing, then take the first element and then check for next to be increasing.
- When the subarray elements are strictly decreasing, then take the first element and then check for next to be decreasing.
- When the subarray elements are strictly decreasing then increasing, then in that case, take the first element and then check for next to decreasing and when it becomes false then check for increasing till the last element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that counts all the reverse// bitonic subarray in arr[]void countReversebitonic(int arr[], int n){ // To store the count of reverse // bitonic subarray int c = 0; // Iterate the array and select // the starting element for (int i = 0; i < n; i++) { // Iterate for selecting the // ending element for subarray for (int j = i; j < n; j++) { // Subarray arr[i to j] int temp = arr[i], f = 0; // For 1 length, increment // the count and continue if (j == i) { c++; continue; } int k = i + 1; // For Decreasing Subarray while (temp > arr[k] && k <= j) { temp = arr[k]; k++; } // Check if only Decreasing if (k > j) { c++; f = 2; } // For Increasing Subarray while (temp < arr[k] && k <= j && f != 2) { temp = arr[k]; k++; } if (k > j && f != 2) { c++; f = 0; } } } // Print the total count of subarrays cout << c << endl;}// Driver Codeint main(){ // Given array arr[] int arr[] = { 2, 3, 1, 4 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call countReversebitonic(arr, N);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function that counts all the reverse// bitonic subarray in arr[]static void countReversebitonic(int arr[], int n){ // To store the count of reverse // bitonic subarray int c = 0; // Iterate the array and select // the starting element for(int i = 0; i < n; i++) { // Iterate for selecting the // ending element for subarray for(int j = i; j < n; j++) { // Subarray arr[i to j] int temp = arr[i], f = 0; // For 1 length, increment // the count and continue if (j == i) { c++; continue; } int k = i + 1; // For decreasing subarray while (temp > arr[k] && k <= j) { temp = arr[k]; k++; } // Check if only decreasing if (k > j) { c++; f = 2; } // For increasing subarray while (k <= j && temp < arr[k] && f != 2) { temp = arr[k]; k++; } if (k > j && f != 2) { c++; f = 0; } } } // Print the total count of subarrays System.out.print(c + "\n");}// Driver Codepublic static void main(String[] args){ // Given array arr[] int arr[] = { 2, 3, 1, 4 }; int N = arr.length; // Function Call countReversebitonic(arr, N);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach # Function that counts all the reverse# bitonic subarray in arr[]def countReversebitonic(arr, n): # To store the count of reverse # bitonic subarray c = 0; # Iterate the array and select # the starting element for i in range(n): # Iterate for selecting the # ending element for subarray for j in range(i, n): # Subarray arr[i to j] temp = arr[i] f = 0; # For 1 length, increment # the count and continue if (j == i): c += 1; continue; k = i + 1; # For Decreasing Subarray while (k <= j and temp > arr[k]): temp = arr[k]; k += 1; # Check if only Decreasing if (k > j): c += 1; f = 2; # For Increasing Subarray 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 the total count of subarrays print(c)# Driver Code# Given array arr[]arr = [ 2, 3, 1, 4 ];# Function CallcountReversebitonic(arr, len(arr));# This code is contributed by grand_master |
C#
// C# program for the above approachusing System;class GFG{// Function that counts all the reverse// bitonic subarray in arr[]static void countReversebitonic(int []arr, int n){ // To store the count of reverse // bitonic subarray int c = 0; // Iterate the array and select // the starting element for(int i = 0; i < n; i++) { // Iterate for selecting the // ending element for subarray for(int j = i; j < n; j++) { // Subarray arr[i to j] int temp = arr[i], f = 0; // For 1 length, increment // the count and continue if (j == i) { c++; continue; } int k = i + 1; // For decreasing subarray while (temp > arr[k] && k <= j) { temp = arr[k]; k++; } // Check if only decreasing if (k > j) { c++; f = 2; } // For increasing subarray while (k <= j && temp < arr[k] && f != 2) { temp = arr[k]; k++; } if (k > j && f != 2) { c++; f = 0; } } } // Print the total count of subarrays Console.Write(c);}// Driver Codepublic static void Main(string[] args){ // Given array arr[] int []arr = { 2, 3, 1, 4 }; int N = arr.Length; // Function Call countReversebitonic(arr, N);}}// This code is contributed by Ritik Bansal |
Javascript
<script>// JavaScript program for the above approach // Function that counts all the reverse// bitonic subarray in arr[]function countReversebitonic(arr, n){ // To store the count of reverse // bitonic subarray let c = 0; // Iterate the array and select // the starting element for(let i = 0; i < n; i++) { // Iterate for selecting the // ending element for subarray for(let j = i; j < n; j++) { // Subarray arr[i to j] let temp = arr[i], f = 0; // For 1 length, increment // the count and continue if (j == i) { c++; continue; } let k = i + 1; // For decreasing subarray while (temp > arr[k] && k <= j) { temp = arr[k]; k++; } // Check if only decreasing if (k > j) { c++; f = 2; } // For increasing subarray while (k <= j && temp < arr[k] && f != 2) { temp = arr[k]; k++; } if (k > j && f != 2) { c++; f = 0; } } } // Print the total count of subarrays document.write(c + "<br/>");}// Driver Code // Given array arr[] let arr = [ 2, 3, 1, 4 ]; let N = arr.length; // Function Call countReversebitonic(arr, N);</script> |
Output:
8
Time Complexity: O(N2), where N is the number of elements in the given array.
Take a part in the ongoing discussion
