atlasworld's blog

Help in this subarray count problem !

By atlasworld, history, 5 years ago, In English

Suppose you are given an Array : a[] = { 0 , 0 , 1 , 0 , 0} . size of array can be large upto 2e5. **** You have to count all the subarrays in which a particular element x occurs more than length(subarray) /2 times

for example if x = 0 :

subarrays are :

{0} index = 1

{0} index = 2

{0} index = 4

{0} index = 5

{0,0} index 1 --> 3

{0,0} index 4 -->5

{0,0,1}

{0,1,0}

{1,0,0}

{0,0,1,0}

{0,1,0,0}

{0,0,1,0,0}

ans = 12.

Any idea !

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you explain more clearly? I don't understand. 'the subarrays in which a particular element x occurs more than length(subarray) times' — the length of the subarray is a maximum number of occurrences of a particular element x. It can't occur more times than the length of the subarray.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oops.. really sorry .. in a rush i did mistake.

    its len/2.

    see if u could help

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 4   Vote: I like it +9 Vote: I do not like it

      I think I've got it in O(n log n) so it is enough for n <= 2e5. Create prefix array in such a way that prefix[i] denotes (number of x's in prefix i — other numbers in prefix i). For exemplary array it will be 1 2 1 2 3. You create it as below:

      for (int i = 1; i <= n; i++) {
        cin >> input;
        prefix[i] = prefix[i - 1];
        if (input == x)
            prefix[i]++;
        else
            prefix[i]--;
}

      This is obviously O(n). Now let's go from the end of the array and for each i, count all the subarrays which start from i+1 and are proper. for(int i = n-1; i >= 0; i--) We can do it in O(log n). Number of subarrays that should be counted is equal to the number of such m: i < m <= n && prefix[m] — prefix[i] > 0. (it means that the prefix 'grows' so there are more x's than other numbers in the subarray). The results will be as below:

      i = 4, count = 1
i = 3, count = 2
i = 2, count = 1
i = 1, count = 3
i = 0, count = 5
============== 12

      How to know how many m's meet this condition for each i? We can keep them in tree. Leaves are all possible values of prefix[m] so there are n+1 of them. Every time we pass the prefix, we add it to the tree in O(log n). It guarantees that i < m <= n. When we want to count m's which meet the second condition, we can do it in O(log n), too. It's just a range query.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        thanks , get the idea ! we can do a range sum on segment tree .

        → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What are the constraints over the elements of the array ?

Is x known beforehand or we need to search for all x that satisfy this property ?

→ Reply