Maximum count of distinct sized subarrays with given sum
Given a binary array arr[] of N integers, the task is to find the maximum count of distinct sized subarrays such that the sum of each subarray is K.
Example:
Input: arr[] = {0, 1, 1 , 0}, K = 2
Output: 3
Explanation: The subset {{0, 1, 1, 0}, {0, 1, 1}, {1, 1}} is the subset of 3 subarrays such that the sum of each subarray is 2 and the size of each subarray is distinct. The subarray {1, 1, 0} also has sum 2 but a subarray of size 3 is already included.Input: arr[] = {0, 1, 0, 0, 0, 1 , 0}, K = 1
Output: 5
Approach: The given problem can be solved with the help of the sliding window algorithm. It can be observed that the sum of a subarray is equal to the count of 1’s in the subarray. Below are the steps to follow:
- Maintain a variable that keeps track of the count of 1’s in the current window.
- If the count of 1’s in the current window is less than K, increase the window size, and similarly if the count of 1’s is greater than K, decrease the window size.
- For windows with K sum, insert their size in a set data structure.
- The number of elements in the set after traversing the complete array is the required answer.
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 size of the largest // subset of subarrays having given sum // and size of each subarray is distinct int maxSubsetSize( int arr[], int N, int K) { // Stores starting index // of the current window int ptr = 0; // Stores distinct subarray // sizes of the subset unordered_set< int > s; // Stores the sum of // current window int curSum = 0; // Loop to traverse over array for ( int i = 0; i < N; i++) { // Update current window sum curSum += arr[i]; // If sum is less that K if (curSum < K) { continue ; } // If sum is more than K if (curSum > K) { // Decrease window size while (curSum > K) { curSum -= arr[ptr++]; } } if (curSum == K) { // Insert size of the // current window s.insert(i - ptr + 1); int t = ptr; // Iterate over all windows // with same sum while (arr[t] == 0) { s.insert(i - t); t++; } } } // Return Answer return s.size(); } // Driver Code int main() { int arr[] = { 0, 1, 1, 0 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 2; cout << maxSubsetSize(arr, N, K); return 0; } |
Java
// Java program for the above approach import java.util.HashSet; class GFG { // Function to find size of the largest // subset of subarrays having given sum // and size of each subarray is distinct static int maxSubsetSize( int arr[], int N, int K) { // Stores starting index // of the current window int ptr = 0 ; // Stores distinct subarray // sizes of the subset HashSet<Integer> s = new HashSet<Integer>(); // Stores the sum of // current window int curSum = 0 ; // Loop to traverse over array for ( int i = 0 ; i < N; i++) { // Update current window sum curSum += arr[i]; // If sum is less that K if (curSum < K) { continue ; } // If sum is more than K if (curSum > K) { // Decrease window size while (curSum > K) { curSum -= arr[ptr++]; } } if (curSum == K) { // Insert size of the // current window s.add(i - ptr + 1 ); int t = ptr; // Iterate over all windows // with same sum while (arr[t] == 0 ) { s.add(i - t); t++; } } } // Return Answer return s.size(); } // Driver Code public static void main(String args[]) { int arr[] = { 0 , 1 , 1 , 0 }; int N = arr.length; int K = 2 ; System.out.println(maxSubsetSize(arr, N, K)); } } // This code is contributed by saurabh_jaiswal. |
Python3
# python3 program for the above approach # Function to find size of the largest # subset of subarrays having given sum # and size of each subarray is distinct def maxSubsetSize(arr, N, K): # Stores starting index # of the current window ptr = 0 # Stores distinct subarray # sizes of the subset s = set () # Stores the sum of # current window curSum = 0 # Loop to traverse over array for i in range ( 0 , N): # Update current window sum curSum + = arr[i] # If sum is less that K if (curSum < K): continue # If sum is more than K if (curSum > K): # Decrease window size while (curSum > K): curSum - = arr[ptr] ptr + = 1 if (curSum = = K): # Insert size of the # current window s.add(i - ptr + 1 ) t = ptr # Iterate over all windows # with same sum while (arr[t] = = 0 ): s.add(i - t) t + = 1 # Return Answer return len ( list (s)) # Driver Code if __name__ = = "__main__" : arr = [ 0 , 1 , 1 , 0 ] N = len (arr) K = 2 print (maxSubsetSize(arr, N, K)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to find size of the largest // subset of subarrays having given sum // and size of each subarray is distinct static int maxSubsetSize( int []arr, int N, int K) { // Stores starting index // of the current window int ptr = 0; // Stores distinct subarray // sizes of the subset HashSet< int > s = new HashSet< int >(); // Stores the sum of // current window int curSum = 0; // Loop to traverse over array for ( int i = 0; i < N; i++) { // Update current window sum curSum += arr[i]; // If sum is less that K if (curSum < K) { continue ; } // If sum is more than K if (curSum > K) { // Decrease window size while (curSum > K) { curSum -= arr[ptr++]; } } if (curSum == K) { // Insert size of the // current window s.Add(i - ptr + 1); int t = ptr; // Iterate over all windows // with same sum while (arr[t] == 0) { s.Add(i - t); t++; } } } // Return Answer return s.Count; } // Driver Code public static void Main(String []args) { int []arr = { 0, 1, 1, 0 }; int N = arr.Length; int K = 2; Console.WriteLine(maxSubsetSize(arr, N, K)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript code for the above approach // Function to find size of the largest // subset of subarrays having given sum // and size of each subarray is distinct function maxSubsetSize(arr, N, K) { // Stores starting index // of the current window let ptr = 0; // Stores distinct subarray // sizes of the subset let s = new Set(); // Stores the sum of // current window let curSum = 0; // Loop to traverse over array for (let i = 0; i < N; i++) { // Update current window sum curSum += arr[i]; // If sum is less that K if (curSum < K) { continue ; } // If sum is more than K if (curSum > K) { // Decrease window size while (curSum > K) { curSum -= arr[ptr++]; } } if (curSum == K) { // Insert size of the // current window s.add(i - ptr + 1); let t = ptr; // Iterate over all windows // with same sum while (arr[t] == 0) { s.add(i - t); t++; } } } // Return Answer return s.size; } // Driver Code let arr = [0, 1, 1, 0]; let N = arr.length; let K = 2; document.write(maxSubsetSize(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(N)