Given an array arr[] of N integers and two integers M and K. The task is to check if the product of the K largest sum of contiguous subarrays is greater than M.
Examples:
Input: arr[] = {10, -4, -2, 7}, M = 659, K = 3
Output: Yes The 3 largest contiguous sums for the subarrays are of the subarrays {10, -4, -2, 7}, {10} and {7} i.e. 11, 10 and 7, the product is 11 * 10 * 7 = 770 which is greater than 659.Input: arr[] = {4, -3, 8}, M = 100, K = 6
Output: No
A brute force approach is to store all the sum of the contiguous subarray in some other array and sort it then calculate the product of the K largest sum and check if the value is greater than M. But in case of the size of the array being too large, the number of continuous subarrays will increase, and hence the auxiliary array will take more space. A better approach is to store the prefix sum of the array in the array itself. Then the sum of the subarray arr[i…j] can be calculated as arr[j] – arr[i – 1]. Now for storing the K largest sum contiguous subarrays, use a min-heap (priority queue) in which only the K maximum sums will be stored at a time. After that for every other element, check if the element is greater than the top element of the min-heap if yes then that element will be inserted into the min-heap and the top element will be popped from the min-heap. In the end, calculate the product of all the elements in the min-heap and check if it is greater than M or not.
Below is the implementation of the above approach:
CPP
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function that returns true is the product // of the maximum K subarrays sums of // arr[] is greater than M bool checkKSum( int arr[], int n, int k, int M) { // Update the array to store the prefix sum for ( int i = 1; i < n; i++) arr[i] = arr[i - 1] + arr[i]; // Min-heap priority_queue< int , vector< int >, greater< int > > Q; // Starting index of the subarray for ( int i = 0; i < n; i++) { // Ending index of the subarray for ( int j = i; j < n; j++) { // To store the sum of the // subarray arr[i...j] int sum = (i == 0) ? arr[j] : arr[j] - arr[i - 1]; // If the queue has less than k elements // then simply push it if (Q.size() < k) Q.push(sum); else { // If the min heap has equal exactly k // elements then check if the current // sum is greater than the smallest // of the current k sums stored if (Q.top() < sum) { Q.pop(); Q.push(sum); } } } } // Calculate the product of // the k largest sum long product = 1; while (!Q.empty()) { product *= Q.top(); Q.pop(); } // If the product is greater than M if (product > M) return true ; return false ; } // Driver code int main() { int a[] = { 10, -4, -2, 7 }; int n = sizeof (a) / sizeof (a[0]); int k = 3, M = 659; if (checkKSum(a, n, k, M)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// JAVA implementation of the approach import java.util.*; class GFG { // Function that returns true is the product // of the maximum K subarrays sums of // arr[] is greater than M public static boolean checkKSum( int arr[], int n, int k, int M) { // Update the array to store the prefix sum for ( int i = 1 ; i < n; i++) arr[i] = arr[i - 1 ] + arr[i]; // Min-heap PriorityQueue<Integer> Q = new PriorityQueue<Integer>(); // Starting index of the subarray for ( int i = 0 ; i < n; i++) { // Ending index of the subarray for ( int j = i; j < n; j++) { // To store the sum of the // subarray arr[i...j] int sum = (i == 0 ) ? arr[j] : arr[j] - arr[i - 1 ]; // If the queue has less than k elements // then simply push it if (Q.size() < k) Q.add(sum); else { // If the min heap has equal exactly k // elements then check if the current // sum is greater than the smallest // of the current k sums stored if (Q.poll() < sum) { // Q.pop(); Q.add(sum); } } } } // Calculate the product of // the k largest sum long product = 1 ; while (Q.isEmpty() == false ) { product = product * Q.poll(); } // If the product is greater than M if (product > M) return true ; return false ; } // Driver code public static void main(String[] args) { int a[] = { 10 , - 4 , - 2 , 7 }; int n = a.length; int k = 3 , M = 659 ; if (checkKSum(a, n, k, M)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Taranpreet |
Python3
# Python3 implementation of the approach # importing heapq python module to implement min heap import heapq # Function that returns true is the product # of the maximum K subarrays sums of # arr[] is greater than M def checkKSum(arr, n, k, M): # Update the array to store the prefix sum for i in range ( 1 , n): arr[i] + = arr[i - 1 ] Q = arr # creating Min-heap with heapify() inbuilt function heapq.heapify(Q) # Starting index of the subarray for i in range (n): # Ending index of the subarray for j in range (i, n): # To store the sum of the # subarray arr[i...j] if i = = 0 : sum = 0 else : sum = arr[j] - arr[i - 1 ] # If the queue has less than k elements # then simply push it if len (Q) < k: Q.append( sum ) heapq.heapify(Q) else : # If the min heap has equal exactly k # elements then check if the current # sum is greater than the smallest # of the current k sums stored if Q[ 0 ] < sum : Q[ 0 ] = sum heapq.heapify(Q) # Calculate the product of # the k largest sum product = 1 for i in Q: product * = i # If the product is greater than M if product > M: return True return False # Driver code if __name__ = = '__main__' : a = [ 10 , - 4 , - 2 , 7 ] n = len (a) k, M = 3 , 659 if checkKSum(a, n, k, M): print ( 'Yes' ) else : print ( 'No' ) '''This Code is contributed by Rajat Kumar (GLAU)''' |
C#
// C# implementation of the approach using System; using System.Collections; public class GFG { // Function that returns true is the product // of the maximum K subarrays sums of // arr[] is greater than M public static bool checkKSum( int [] arr, int n, int k, int M) { // Update the array to store the prefix sum for ( int i = 1; i < n; i++) arr[i] = arr[i - 1] + arr[i]; // Min-heap SortedList Q = new SortedList(); // Starting index of the subarray for ( int i = 0; i < n; i++) { // Ending index of the subarray for ( int j = i; j < n; j++) { // To store the sum of the // subarray arr[i...j] int sum = (i == 0) ? arr[j] : arr[j] - arr[i - 1]; // If the queue has less than k elements // then simply push it if (Q.Count < k) Q.Add(sum, sum); else { // If the min heap has equal exactly k // elements then check if the current // sum is greater than the smallest // of the current k sums stored int elem = ( int )Q.GetByIndex(0); Q.RemoveAt(0); if (elem < sum) { // Q.pop(); Q.Add(sum, sum); } } } } // Calculate the product of // the k largest sum long product = 1; while (Q.Count != 0) { int elem = ( int )Q.GetByIndex(0); Q.RemoveAt(0); product = product * elem; } // If the product is greater than M if (product > M) return true ; return false ; } public static void Main( string [] args) { int [] a = { 10, -4, -2, 7 }; int n = a.Length; int k = 3, M = 659; if (checkKSum(a, n, k, M)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by phasing17 |
Javascript
// JavaScript implementation of the approach // Function that returns true is the product // of the maximum K subarrays sums of // arr[] is greater than M function checkKSum(arr, n, k, M) { var elem; var sum; // Update the array to store the prefix sum for ( var i = 1; i < n; i++) arr[i] += arr[i - 1]; // Min-heap let Q = arr; // Starting index of the subarray for ( var i = 0; i < n; i++) { // Ending index of the subarray for ( var j = i; j < n; j++) { // To store the sum of the // subarray arr[i...j] if (i == 0) sum = 0; else sum = arr[j] - arr[i - 1]; Q.sort(); // If the queue has less than k elements // then simply push it if (Q.length < k) { Q.push(sum); } else { // If the min heap has equal exactly k // elements then check if the current // sum is greater than the smallest // of the current k sums stored if (Q[0] < sum) { Q[0] = sum; } Q.sort(); } } } // Calculate the product of // the k largest sum var product = 1; for ( var elem of Q) product *= elem; // If the product is greater than M if (product > M) return true ; return false ; } let a = [ 10, -4, -2, 7 ]; let n = a.length; let k = 3; let M = 659; if (checkKSum(a, n, k, M)) console.log( "Yes" ); else console.log( "No" ); // This code is contributed by phasing17 |
Yes
Time Complexity: O(n2log n)
Auxiliary Space: O(n)