Count of Subarrays with sum equals k in given Binary Array
source link: https://www.geeksforgeeks.org/count-of-subarrays-with-sum-equals-k-in-given-binary-array//
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Count of Subarrays with sum equals k in given Binary Array
- Last Updated : 18 Apr, 2023
Given a binary array arr[] and an integer k, the task is to find the count of non-empty subarrays with a sum equal to k.
Examples:
Input: arr[] = {1, 0, 1, 1, 0, 1}, k = 2
Output: 6
Explanation: All valid subarrays are: {1, 0, 1}, {0, 1, 1}, {1, 1}, {1, 0, 1}, {0, 1, 1, 0}, {1, 1, 0}.Input: arr[] = {0, 0, 0, 0, 0}, k = 0
Output: 15
Explanation: All subarrays have a sum equal to 0, and there are a total of 15 subarrays.
Approach: This can be solved with the following idea:
We can solve this problem using a sliding window approach. We can keep track of the prefix sum of the array while iterating through it, and use two pointers to maintain a subarray with a sum equal to the given goal. We can calculate the number of subarrays with a maximum not greater than a goal and subtract the number of subarrays with a maximum not greater than goal-1 to get the final result.
Below are the steps involved in the implementation of the code:
- Count the number of subarrays having a sum at most k and k-1 by calling the function atmost().
- Return the difference in their count as a result.
Below is the implementation of the above approach:
// C++ Implementation of code#include <iostream>#include <vector>using namespace std;// Function to find count of subarrays// with sum at most kint atmost(vector<int>& nums, int k){if (k < 0)return 0;int l = 0, cnt = 0;int res = 0;for (int i = 0; i < nums.size(); i++) {cnt += nums[i];// Adjust the window sum by removing// elements from the left until it is// at most kwhile (cnt > k)cnt -= nums[l++];// Add the count of subarrays with// sum at most k for the current windowres += (i - l + 1);}return res;}// Function to find count of subarrays// with sum equal to kint numSubarraysWithSum(vector<int>& nums, int goal){// Call atmost(nums, goal) and atmost// (nums, goal-1) to get the count of// subarrays with sum at most goal// and sum at most goal-1 respectively,// then subtract them to get the count// of subarrays with sum exactly// equal to goalreturn atmost(nums, goal) - atmost(nums, goal - 1);}// Driver codeint main(){vector<int> arr1 = { 1, 0, 1, 1, 0, 1 };int k1 = 2;// Function callcout << numSubarraysWithSum(arr1, k1) << endl;return 0;} |
Count of subarrays with sum 2: 6 Count of subarrays with sum 0: 15
Time Complexity: O(n)
Auxiliary Space:O(1)
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK