Total binary subarrays with ratio x:y

Правка en2, от anupomkar, 2022-07-31 18:53:17

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.

Теги sliding window, subarray, count subarray

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский anupomkar 2022-07-31 18:53:17 18
en1 Английский anupomkar 2022-07-31 18:50:06 659 Initial revision (published)