A coin-flip experiment is logged as a sequence of n outcomes, each 0 (tails) or 1 (heads). Count how many contiguous subarrays contain exactly as many 0s as 1s. A subarray is a run of consecutive entries, and two subarrays that occupy different index ranges are counted separately even if their contents match.
Line 1: an integer n.
Line 2: n space-separated integers, each 0 or 1.
A single integer: the number of contiguous subarrays with equal counts of 0 and 1.
Example 1
Input
4 0 1 0 1
Expected
4
Explanation
The balanced subarrays are [0 1], [1 0], [0 1] and the whole [0 1 0 1] -- four in total.
Example 2
Input
3 1 1 1
Expected
0
Explanation
There are no 0s, so no subarray can balance 0s and 1s: the count is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →