# Leetcode 930 - Binary Subarrays With Sum

### Understanding the problem

You are given an array of binary integers `arr` and an integer `s`.

Return the number of non-empty subarrays of `arr` that have a sum equal to `s`.

A subarray is a contiguous subsequence of the array.

Example:

Input: arr = [1,0,1,0,1], s = 2

Output: 4

Explanation: There are 4 subarrays with a sum of 2:

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

Input: arr = [0,0,0,0,0], s = 0

Output: 15

Explanation: There are 15 subarrays with a sum of 0:

[0]

[0]

[0]

[0]

[0]

[0,0]

[0,0]

[0,0]

[0,0]

[0,0]

[0,0,0]

[0,0,0]

[0,0,0]

[0,0,0]

[0,0,0,0]

Constraints:

• `1 <= arr.length <= 10^5`
• `0 <= s <= arr.length`

One approach to solve this problem is to use a prefix sum array.

We can start by initializing a prefix sum array `prefix` where `prefix[i]` is the sum of the first `i` elements of `arr`.

Then, we can iterate over the elements of `arr` and use the prefix sum array to count the number of subarrays with a sum of `s`.

For each `i`, we can find the number of subarrays that end at `i` and have a sum of `s` by looking at the number of subarrays that start at `j` and end at `i-1` and have a sum of `s - arr[i]`. We can do this by keeping track of the frequency of each sum in a dictionary.

We can initialize the dictionary with a key `0` and a value of `1`. This is because there is always one subarray with a sum of 0, which is the empty subarray.

For each `i`, we increment the frequency of the sum `s - arr[i]` in the dictionary and add the frequency to the count of subarrays that end at `i` and have a sum of `s`.

Finally, we return the count of subarrays.

Now let’s implement the solution in Python.

``````class Solution:
def numSubarraysWithSum(self, arr: List[int], s: int) -> int:
# Initialize prefix sum array
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
prefix[i+1] = prefix[i] + arr[i]

# Initialize dictionary with a key 0 and a value of 1
d = {0: 1}
count = 0
# Iterate over elements of arr
for i in range(len(arr)):
# Increment the frequency of the sum s - arr[i] in the dictionary
# Add the frequency to the count of subarrays that end at i and have a sum of s
count += d.get(prefix[i+1] - s, 0)
d[prefix[i+1]] = d.get(prefix[i+1], 0) + 1

# Return count
return count
``````

Now we can test our solution with some test cases.

``````arr = [1,0,1,0,1]
s = 2
assert numSubarraysWithSum(arr, s) == 4

arr = [0,0,0,0,0]
s = 0
assert numSubarraysWithSum(arr, s) == 15

arr = [1,1,1,1,1]
s = 1
assert numSubarraysWithSum(arr, s) == 15

arr = [0,1,1,1,1]
s = 2
assert numSubarraysWithSum(arr, s) == 7

arr = [1,1,1,1,0]
s = 2
assert numSubarraysWithSum(arr, s) == 8
``````

All the test cases pass, which means our solution is correct.

That’s it! We have successfully implemented a solution to find the number of non-empty subarrays of `arr` that have a sum equal to `s` using a prefix sum array and a dictionary.