Given an array arr[] of size N and an integer K., The task is to count the number of subarrays with unique sum with sum at most K.
Examples:
Input: N = 3, arr[] = {1, 0, 1}, K = 1
Output: 2
Explanation: All Subarrays are [1], [0], [1], [1, 0], [0, 1], [1, 0, 1] & The sum of these subarrays are {1, 0, 1, 1, 1, 2} respectively. There are only 2 distinct possible sums less than or equal to 1
Input: N = 1, arr[] = {1}, K = 0
Output: 0
Approach: The task can be solved by calculating sums of each subarray and storing them in a HashMap. Iterate over the HashMap, and increment the count, if the sum is at most K
Below is the implementation of the above approach
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the valid sumsvoid solve(int arr[], int n, int k){ // Store the distinct subarray sums unordered_map<int, int> occ; int cur = 0; for (int i = 0; i < n; i++) { cur = 0; for (int j = i; j < n; j++) { cur += arr[j]; occ[cur]++; } } // Stores the answer int ans = 0; for (auto x : occ) { if (x.first <= k) ans++; } cout << ans << endl;}// Driver Codeint main(){ int N = 3, K = 1; int arr[3] = { 1, 0, 1 }; solve(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to calculate the valid sumsstatic void solve(int arr[], int n, int k){ // Store the distinct subarray sums HashMap<Integer,Integer> occ = new HashMap<Integer,Integer>(); int cur = 0; for (int i = 0; i < n; i++) { cur = 0; for (int j = i; j < n; j++) { cur += arr[j]; if(occ.containsKey(cur)){ occ.put(cur, occ.get(cur)+1); } else{ occ.put(cur, 1); } } } // Stores the answer int ans = 0; for (Map.Entry<Integer,Integer> x : occ.entrySet()) { if (x.getKey() <= k) ans++; } System.out.print(ans +"\n");}// Driver Codepublic static void main(String[] args){ int N = 3, K = 1; int arr[] = { 1, 0, 1 }; solve(arr, N, K);}}// This code is contributed by 29AjayKumar |
Python3
# python program for the above approach# Function to calculate the valid sumsdef solve(arr, n, k): # Store the distinct subarray sums occ = {} cur = 0 for i in range(0, n): cur = 0 for j in range(i, n): cur += arr[j] if cur in occ: occ[cur] += 1 else: occ[cur] = 1 # Stores the answer ans = 0 for x in occ: if (x <= k): ans += 1 print(ans)# Driver Codeif __name__ == "__main__": N = 3 K = 1 arr = [1, 0, 1] solve(arr, N, K) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to calculate the valid sums static void solve(int[] arr, int n, int k) { // Store the distinct subarray sums Dictionary<int, int> occ = new Dictionary<int, int>(); int cur = 0; for (int i = 0; i < n; i++) { cur = 0; for (int j = i; j < n; j++) { cur += arr[j]; if (!occ.ContainsKey(cur)) occ[cur] = 0; else occ[cur]++; } } // Stores the answer int ans = 0; foreach(KeyValuePair<int, int> x in occ) { if (x.Key <= k) ans++; } Console.WriteLine(ans); } // Driver Code public static void Main() { int N = 3, K = 1; int[] arr = { 1, 0, 1 }; solve(arr, N, K); }}// This code is contributed by ukasp. |
Javascript
<script>// JavaScript code for the above approach // Function to calculate the valid sumsfunction solve(arr, n, k){ // Store the distinct subarray sums let occ = new Map(); let cur = 0; for(let i = 0; i < n; i++) { cur = 0; for(let j = i; j < n; j++) { cur += arr[j]; if (occ.has(cur)) { occ.set(cur, occ.get(cur) + 1) } else { occ.set(cur, 1); } } } // Stores the answer let ans = 0; for(let[key, value] of occ) { if (key <= k) ans++; } document.write(ans + '<br>');}// Driver Codelet N = 3, K = 1;let arr = [ 1, 0, 1 ];solve(arr, N, K);// This code is contributed by Potta Lokesh</script> |
Output
2
Time Complexity: O(N2)
Auxiliary Space: O(N)
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!