Given an array arr[] consisting of N positive integers, the task is to find the count of subarrays such that the maximum element of the subarray is greater than twice the maximum of all other elements of the array.
Examples:
Input: arr[] = {1, 6, 10, 9, 7, 3}
Output: 4
Explanation:
Below are the subarrays satisfying the given condition:
- Consider the subarray {6, 10, 9, 7}. Now the maximum element of this subarray is 10 which is greater than twice the maximum elements of the remaining array elements i.e., 2*max{1, 3} = 2*3 = 6.
- Consider the subarray {6, 10, 9, 7, 3}. Now the maximum element of this subarray is 10 which is greater than twice the maximum elements of the remaining array elements i.e., 2*max{1} = 2*1 = 2.
- Consider the subarray {1, 6, 10, 9, 7}. Now the maximum element of this subarray is 10 which is greater than twice the maximum elements of the remaining array elements i.e., 2*max{3} = 2*3 = 6.
- Consider the subarray {1, 6, 10, 9, 7, 3}. Now the maximum element of this subarray is 10 which is greater than twice the maximum elements of the remaining array elements i.e., 2*max{} = 2*0 = 0.
Therefore, the total number of subarrays is 4.
Input: arr[] = {1, 10, 2, 3}
Output: 6
Naive Approach: The simplest approach to solve the given problem is to generate all possible subarrays of the given array arr[] and then count the number of subarrays having a maximum element greater than twice the maximum of all other elements. After checking for all the subarrays, print the count of the subarray obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to find count of subarrays// which have max element greater than// twice maximum of all other elementsvoid countSubarray(int arr[], int n){ // Stores the count of subarrays int count = 0; // Generate all possible subarrays for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { // Stores the maximum element // of the subarray int mxSubarray = 0; // Stores the maximum of all // other elements int mxOther = 0; // Find the maximum element // in the subarray [i, j] for (int k = i; k <= j; k++) { mxSubarray = max(mxSubarray, arr[k]); } // Find the maximum of all // other elements for (int k = 0; k < i; k++) { mxOther = max( mxOther, arr[k]); } for (int k = j + 1; k < n; k++) { mxOther = max( mxOther, arr[k]); } // If the maximum of subarray // is greater than twice the // maximum of other elements if (mxSubarray > (2 * mxOther)) count++; } } // Print the maximum value obtained cout << count;}// Driver Codeint main(){ int arr[] = { 1, 6, 10, 9, 7, 3 }; int N = sizeof(arr) / sizeof(arr[0]); countSubarray(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to find count of subarrays// which have max element greater than// twice maximum of all other elementspublic static void countSubarray(int arr[], int n){ // Stores the count of subarrays int count = 0; // Generate all possible subarrays for(int i = 0; i < n; i++) { for(int j = i; j < n; j++) { // Stores the maximum element // of the subarray int mxSubarray = 0; // Stores the maximum of all // other elements int mxOther = 0; // Find the maximum element // in the subarray [i, j] for(int k = i; k <= j; k++) { mxSubarray = Math.max( mxSubarray, arr[k]); } // Find the maximum of all // other elements for(int k = 0; k < i; k++) { mxOther = Math.max(mxOther, arr[k]); } for(int k = j + 1; k < n; k++) { mxOther = Math.max(mxOther, arr[k]); } // If the maximum of subarray // is greater than twice the // maximum of other elements if (mxSubarray > (2 * mxOther)) count++; } } // Print the maximum value obtained System.out.println(count);}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 6, 10, 9, 7, 3 }; int N = arr.length; countSubarray(arr, N);}}// This code is contributed by Potta Lokesh |
Python3
# Python 3 program for the above approach# Function to find count of subarrays# which have max element greater than# twice maximum of all other elementsdef countSubarray(arr, n): # Stores the count of subarrays count = 0 # Generate all possible subarrays for i in range(n): for j in range(i, n, 1): # Stores the maximum element # of the subarray mxSubarray = 0 # Stores the maximum of all # other elements mxOther = 0 # Find the maximum element # in the subarray [i, j] for k in range(i, j + 1, 1): mxSubarray = max(mxSubarray, arr[k]) # Find the maximum of all # other elements for k in range(0, i, 1): mxOther = max(mxOther, arr[k]) for k in range(j + 1,n,1): mxOther = max(mxOther, arr[k]) # If the maximum of subarray # is greater than twice the # maximum of other elements if (mxSubarray > (2 * mxOther)): count += 1 # Print the maximum value obtained print(count)# Driver Codeif __name__ == '__main__': arr = [1, 6, 10, 9, 7, 3] N = len(arr) countSubarray(arr, N) # This code is contributed by bgangwar59. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find count of subarrays// which have max element greater than// twice maximum of all other elementsstatic void countSubarray(int []arr, int n){ // Stores the count of subarrays int count = 0; // Generate all possible subarrays for(int i = 0; i < n; i++) { for(int j = i; j < n; j++) { // Stores the maximum element // of the subarray int mxSubarray = 0; // Stores the maximum of all // other elements int mxOther = 0; // Find the maximum element // in the subarray [i, j] for(int k = i; k <= j; k++) { mxSubarray = Math.Max(mxSubarray, arr[k]); } // Find the maximum of all // other elements for(int k = 0; k < i; k++) { mxOther = Math.Max(mxOther, arr[k]); } for(int k = j + 1; k < n; k++) { mxOther = Math.Max(mxOther, arr[k]); } // If the maximum of subarray // is greater than twice the // maximum of other elements if (mxSubarray > (2 * mxOther)) count++; } } // Print the maximum value obtained Console.Write(count);}// Driver Codepublic static void Main(){ int []arr = { 1, 6, 10, 9, 7, 3 }; int N = arr.Length; countSubarray(arr, N);}}// This code is contributed by SURENDRA_GANGWAR |
Javascript
<script>// JavaScript program for the above approach// Function to find count of subarrays// which have max element greater than// twice maximum of all other elementsfunction countSubarray(arr, n){ // Stores the count of subarrays let count = 0; // Generate all possible subarrays for(let i = 0; i < n; i++) { for(let j = i; j < n; j++) { // Stores the maximum element // of the subarray let mxSubarray = 0; // Stores the maximum of all // other elements let mxOther = 0; // Find the maximum element // in the subarray [i, j] for(let k = i; k <= j; k++) { mxSubarray = Math.max(mxSubarray, arr[k]); } // Find the maximum of all // other elements for(let k = 0; k < i; k++) { mxOther = Math.max(mxOther, arr[k]); } for(let k = j + 1; k < n; k++) { mxOther = Math.max( mxOther, arr[k]); } // If the maximum of subarray // is greater than twice the // maximum of other elements if (mxSubarray > (2 * mxOther)) count++; } } // Print the maximum value obtained document.write(count);}// Driver Codelet arr = [ 1, 6, 10, 9, 7, 3 ];let N = arr.length;countSubarray(arr, N);// This code is contributed by Potta Lokesh </script> |
Output:
4
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized using the observation that the maximum element of the array will always be a part of the subarray and all elements having a value greater than half of the maximum element is also included in the subarray. Follow the steps below to solve the problem:
- Initialize a variable, say mx that stores the maximum element of the array.
- Initialize two variables L and R to store the left and the right endpoints of the subarray.
- Iterate over the range [0, N – 1] using the variable i and if the value of 2*arr[i] is greater than mx then initialize L to i and break from the loop.
- Iterate over the range [N – 1, 0] in a reverse manner using the variable i and if the value of 2*arr[i] is greater than mx then initialize R to i and break from the loop.
- After completing the above steps, print the value of (L + 1)*(N – R) as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find count of subarrays// which have max element greater than// twice maximum of all other elementsvoid countSubarray(int arr[], int n){ int count = 0, L = 0, R = 0; // Stores the maximum element of // the array int mx = *max_element(arr, arr + n); // Traverse the given array for (int i = 0; i < n; i++) { // If the value of 2*arr[i] is // greater than mx if (arr[i] * 2 > mx) { // Update the value of L // and break out of loop L = i; break; } } for (int i = n - 1; i >= 0; i--) { // If the value 2*arr[i] is // greater than mx if (arr[i] * 2 > mx) { // Update the value of R // and break out of loop R = i; break; } } // Print the final answer cout << (L + 1) * (n - R);}// Driver Codeint main(){ int arr[] = { 1, 6, 10, 9, 7, 3 }; int N = sizeof(arr) / sizeof(arr[0]); countSubarray(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find count of subarrays // which have max element greater than // twice maximum of all other elements static void countSubarray(int[] arr, int n) { int L = 0, R = 0; // Stores the maximum element of // the array int mx = Integer.MIN_VALUE; for (int i = 0; i < n; i++) mx = Math.max(mx, arr[i]); // Traverse the given array for (int i = 0; i < n; i++) { // If the value of 2*arr[i] is // greater than mx if (arr[i] * 2 > mx) { // Update the value of L // and break out of loop L = i; break; } } for (int i = n - 1; i >= 0; i--) { // If the value 2*arr[i] is // greater than mx if (arr[i] * 2 > mx) { // Update the value of R // and break out of loop R = i; break; } } // Print the final answer System.out.println((L + 1) * (n - R)); } // Driver Code public static void main(String[] args) { int[] arr = { 1, 6, 10, 9, 7, 3 }; int N = arr.length; countSubarray(arr, N); }}// This code is contributed by rishavmahato348. |
Python3
# Python3 program for the above approach# Function to find count of subarrays# which have max element greater than# twice maximum of all other elementsdef countSubarray(arr, n): count = 0 L = 0 R = 0 # Stores the maximum element of # the array mx = max(arr) # Traverse the given array for i in range(n): # If the value of 2*arr[i] is # greater than mx if (arr[i] * 2 > mx): # Update the value of L # and break out of loop L = i break i = n - 1 while (i >= 0): # If the value 2*arr[i] is # greater than mx if (arr[i] * 2 > mx): # Update the value of R # and break out of loop R = i break i -= 1 # Print the final answer print((L + 1) * (n - R))# Driver Codeif __name__ == '__main__': arr = [ 1, 6, 10, 9, 7, 3 ] N = len(arr) countSubarray(arr, N) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;class GFG { // Function to find count of subarrays // which have max element greater than // twice maximum of all other elements static void countSubarray(int[] arr, int n) { int L = 0, R = 0; // Stores the maximum element of // the array int mx = Int32.MinValue; for (int i = 0; i < n; i++) mx = Math.Max(mx, arr[i]); // Traverse the given array for (int i = 0; i < n; i++) { // If the value of 2*arr[i] is // greater than mx if (arr[i] * 2 > mx) { // Update the value of L // and break out of loop L = i; break; } } for (int i = n - 1; i >= 0; i--) { // If the value 2*arr[i] is // greater than mx if (arr[i] * 2 > mx) { // Update the value of R // and break out of loop R = i; break; } } // Print the final answer Console.WriteLine((L + 1) * (n - R)); } // Driver Code public static void Main() { int[] arr = { 1, 6, 10, 9, 7, 3 }; int N = arr.Length; countSubarray(arr, N); }}// This code is contributed by ukasp. |
Javascript
<script>// javascript program for the above approach// Function to find count of subarrays// which have max element greater than// twice maximum of all other elementsfunction countSubarray(arr, n){ var count = 0, L = 0, R = 0; // Stores the maximum element of // the array var mx = Math.max.apply(null, arr); var i; // Traverse the given array for (i = 0; i < n; i++) { // If the value of 2*arr[i] is // greater than mx if (arr[i] * 2 > mx) { // Update the value of L // and break out of loop L = i; break; } } for (i = n - 1; i >= 0; i--) { // If the value 2*arr[i] is // greater than mx if (arr[i] * 2 > mx) { // Update the value of R // and break out of loop R = i; break; } } // Print the final answer document.write((L + 1) * (n - R));}// Driver Code var arr = [1, 6, 10, 9, 7, 3] var N = arr.length; countSubarray(arr, N);// This code is contributed by ipg2016107.</script> |
Output:
4
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
