Skip to main content

Intuit

Intuit OA-3 2023

Problem Description

Emma is playing a game with a sequence made up of only 0's and 1's. She wants to determine how many subarrays have a specific ratio of 0's to 1's, which is given by the ratio X:Y. However, as the sequence grows longer, Emma finds it difficult to manually count the subarrays. Can you assist her in finding the solution?

Input Format

  • The first line contains an integer N, representing the length of the sequence.
  • The second line contains N space-separated integers (either 0 or 1).
  • The third line contains two space-separated integers X and Y, denoting the desired ratio of 0's to 1's.

Output Format

Print the total number of subarrays where the ratio of 0's to 1's matches X:Y. The answer should be returned modulo (10^9 + 7).

Constraints

  • 1 ≤ N ≤ 10^5
  • 1 ≤ X ≤ 10^5
  • 1 ≤ Y ≤ 10^5

Example

Sample Input:

4
0 1 0 1
1 1

Sample Output:

4

Explanation:

The valid subarrays where the ratio of 0's to 1's is 1:1 are:

  • ([01])
  • (0 [10] 1)
  • (01 [01])
  • ([0 1 0 1])

Thus, the output is 4.