### atlasworld's blog

By atlasworld, history, 4 years ago,

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 !

• -4

| Write comment?
 » 4 years ago, # |   0 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.
•  » » 4 years ago, # ^ |   0 oops.. really sorry .. in a rush i did mistake.its len/2. see if u could help
•  » » » 4 years ago, # ^ | ← Rev. 4 →   +9 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.
•  » » » » 4 years ago, # ^ |   +3 thanks , get the idea ! we can do a range sum on segment tree .
 » 4 years ago, # | ← Rev. 2 →   0 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 ?