Neeraj_Kumar_Coder's blog

By Neeraj_Kumar_Coder, history, 7 weeks ago, In English

Statement

You are given an array consisting of only 0, 1 and 2. Also given two integers x and y. Your task is to find the number of subarrays with ratio of frequency of 0 and 1 being x : y.

Input

The first line of input contains and integer n, denoting the number of elements in the array.
The next line contains n space separated integers denoting elements of array.
The next line contains two integers x and y.

Output

Output the number of subarrays having 0's and 1's in the ratio x : y.

CONSTRAINTS

2 <= n <= 1e5
1 <= x, y <= n

SAMPLE TEST CASE

5
0 1 2 0 1
1 1

OUTPUT

6
 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Practically the same solution as described here by maxwellzen. The only difference is that in the Prefix Sum you should assign a value of 0 to all 2s in the original array (since they don't affect the ratio of 0s and 1s). Afterwards, remove all subarrays that contain only 2s, since they are invalid. To count these such subarrays, you can find all groups of consecutive 2s. Say a group has size $$$S$$$, then you should remove from the final answer $$$\frac{S \cdot (S - 1)}{2}$$$

EDIT: Should be $$$\frac{S \cdot (S + 1)}{2}$$$ instead of $$$\frac{S \cdot (S - 1)}{2}$$$

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Extremely minor edit, but I think it should be $$$\frac{S \cdot (S+1)}{2}$$$ since there are $$$S+1$$$ endpoints to choose from in a block of $$$S$$$.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was solving the same problem on an online judge. I didn't came up with the idea that I can just substract S*(S+1)/2 to remove consecutive 2 blocks. And I wrote some complex implementation and got 2/9 Test cases failed

    Thanks for the explanation

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please upload the code I am not able to understand

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

let $$$prefixZero[I]$$$ hold count of prefix sum of frequency of number of 0's till index $$$i$$$ and similarly $$$prefixOne[I]$$$ hold count of prefix sum of frequency of number of 1's till index $$$i$$$

then we have to basically find number subarrays from $$$l$$$ to $$$r$$$ such that :-

$$$= \frac{prefixZero[r] - prefixZero[l - 1]} {prefixOne[r] - prefixOne[l - 1]} = \frac {x}{y}$$$

$$$= y * prefixZero[r] - y * prefixZero[l - 1] = x * prefixOne[r] - x * prefixOne[l - 1]$$$

$$$= x * prefixOne[l - 1] - y * prefixZero[l - 1] = x * prefixOne[r] - y * prefixZero[r]$$$

let function $$$f(i) = x * prefixOne[i] - y * prefixZero[i]$$$

so basically we have find all subarrays $$$l$$$ to $$$r$$$ such that $$$f(l-1) = f(r)$$$

iterate for every index, and map for indices where f(i) is same, excluding where both, ones and zeros are 0

for every index $$$I$$$ where $$$f(i)$$$ is same, every endpoint is a candidate with each other, so add $$$len*(len-1)/2$$$ to and, where $$$len$$$ is number of indices where $$$f(i)$$$ is same

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks dude. I learned prefix sum by your explanation. I didn't knew prefix sum before .

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      my post doesn't explain prefix sum if it meant sarcasm, it was quite a lame one

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well you told the approach i was not familiar with. Sorry if it sounded like sarcasm.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I am sorry for misunderstanding,

          however

          technically speaking the method is find range sum by using prefixSum as a tool

          I am glad you liked it

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, I tried you method and it did not seem to work can you let me know what is wrong here:

    int Count(vector<int> nums, int n, int x, int y)
    {
    	int count = 0;
    	vector<int> pre0(n);
    	pre0[0] = nums[0] == 0 ? 1 : 0;
    	for (int i = 1; i < n; i++)
    		pre0[i] = pre0[i - 1] + (nums[i] == 0 ? 1 : 0);
    	
    	vector<int> pre1(n);
    	pre1[0] = nums[0] == 1 ? 1 : 0;
    	for (int i = 1; i < n; i++)
    		pre1[i] = pre1[i - 1] + (nums[i] == 1 ? 1 : 0);
    	
    	unordered_map<int, int> map;
    	for (int i = 0; i < n; i++){
    		if (pre0[i] == 0 && pre1[i] == 0)
    			continue;
    		int f = (x * pre1[i]) - (y * pre0[i]);
    		map[f]++;
    	}
    	for (auto &i : map)
    		count += (i.second * (i.second - 1)) / 2;
    	cout << count;
    	return 0;
    }
    

    For the above input : nums = {0,1,2,0,1}, x=1, y=1; I got the output 4.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your code isn't having the condition for l = 0 and also you should remove the subarrays having neither 0 nor 1 i.e. consecutive subarrays containing 2.

      My code

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

WhyWhy