atlasworld's blog

By atlasworld, history, 9 months 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

»
9 months 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.

  • »
    »
    9 months 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

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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 .

»
9 months 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 ?