A row of parking bays is given as bays, where 0 means empty and 1 means occupied. A divider placed before index i (1 <= i < n) is fair when the number of empty bays on its left equals the number of occupied bays on its right. Count the fair divider positions.
Examples
Input: bays = [0, 1, 0, 1, 1]
Output: 1
Explanation: before index 3 the left part [0, 1, 0] has 2 empties and the right part [1, 1] has 2 occupied bays. No other position is fair.
Input: bays = [0, 1]
Output: 1
Input: bays = [1, 1, 1]
Output: 0
Constraints
2 <= len(bays) <= 10**5, each entry is0or1- Target complexity: O(n) time. Recounting both sides for every position is too slow.
Goals
- Precompute a count over the suffix and a running count over the prefix
- Test every split point in O(1)