Total binary subarrays with with x:y 0's and 1's

Revision en1, by anupomkar, 2022-07-31 18:50:06

Given a binary array, find the total number of subarrays with the ratio of 0's and 1's equal to x:y.

Constraints:

n = arr.length

2<=n<=1e5

1<=x,y<=n

Example: arr = [0,1,0,1] x = 1 y = 1

Output: 4

Explanation: The four possible subarrays are as follows:

[0 1] 0 1 --> [0,1]

0 [1 0] 1 --> [1,0]

0 1 [0 1] --> [0,1]

[0 1 0 1] --> [0,1,0,1]

With the given constraints, expecting solution no worse than O(n)

P.s: Maybe the problem can be solved using the sliding window technique. But unable to apply it due to ratio constraint.

Tags sliding window, subarray, count subarray

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English anupomkar 2022-07-31 18:53:17 18
en1 English anupomkar 2022-07-31 18:50:06 659 Initial revision (published)