The challenge
Count nonempty contiguous subarrays of a binary array whose sum equals goal.
Every value is 0 or 1; goal ≥ 0. Empty input returns 0.
Example
[1, 0, 1, 0, 1], goal = 2 → 4; [0, 0, 0], goal = 0 → 6.
Use the walkthrough below to inspect the input and each state change.
See Exact binary sum, step by step
Expand, shrink, and inspect the window state.
5 elements · zero-based indicestarget = 2
Current windowRecorded answerOutside window
- Left
- 0
- Right
- -1
- Length
- 0
Step 01 / 29
Start with an empty window
Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.
left = 0; right = −1Answer so far
0
View exact input
Input: [1,0,1,0,1] · target = 2
Current window is empty.
Put it into code
Nonnegative values support an at-most sum window. Subtract counts for goal and goal − 1 to include every valid zero-prefixed or zero-suffixed subarray.
Indices are zero-based. C++ uses C++17 or later.
def binary_subarrays_sum(nums, goal):
def at_most(budget):
if budget < 0:
return 0
left = total = window_sum = 0
for right, value in enumerate(nums):
window_sum += value
while window_sum > budget:
window_sum -= nums[left]
left += 1
total += right - left + 1
return total
return at_most(goal) - at_most(goal - 1)#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
long long binary_subarrays_sum(const vector<int>& nums, int goal) {
auto at_most = [&](int budget) -> long long {
if (budget < 0) return 0;
int left = 0, sum = 0;
long long total = 0;
for (int r = 0; r < (int)nums.size(); ++r) {
sum += nums[r];
while (sum > budget) sum -= nums[left++];
total += r - left + 1;
}
return total;
};
return at_most(goal) - at_most(goal - 1);
}