2
$\begingroup$

We have given array $V$ of $N$ integers, we want to count the number of subarrays of the array such that each elements in the subarray either doesn't occur at all, or it occurs odd number of times.

Subarray is subset of array that is contiguous part of the array.

For example $N = 4, V = \{1, 1, 1, 2\}$. The result is $7$, and the subarrays we want to count are as follow: $[1, 1], [2,2], [3,3], [4,4], [1, 3], [1, 4], [3,4]$. Note that the intervals I wrote mean the part of the array starting at index $i$ finishing at $j$.

I coded the $O(N^2)$ algorithm but I know that there is faster way to do it. So, I tried to do some observations and to use XOR to count them, but I couldn't find anything that will work stable.

$\endgroup$
  • $\begingroup$ Try to count the number of subarrays not satisfying the condition, it should be simpler :) $\endgroup$ – VashTheStampede Aug 7 '18 at 8:13
  • $\begingroup$ Could you elaborate it more, because counting all subarrays that have at least one number occuring even number of times is not really easier for me. $\endgroup$ – someone12321 Aug 7 '18 at 10:34
  • $\begingroup$ It's easier because you don't have to check the number of occurrences of ALL values, but you just have to consider the occurrences of a specific value. Fix v=V[0] and suppose that the next occurrences of v are V[i_1], V[i_2], ... then you can count how many subarrays starts at 0 and have exactly 2 occurrences of v, next you count subarrays starting at 0 that have 4 occurrences of v, then 6 and so on. Next you fix V[1] and you do the same and so on. This operation can be done in linear time and it's easy to see that at the end you counted all subarrays with even occurrences exactly once. $\endgroup$ – VashTheStampede Aug 7 '18 at 10:45
  • $\begingroup$ Of course mine is not a complete algo, its just an hint. Another thing is that the algo I have in mind is O(nlogn) and it starts re-mapping all values in the range {1,...,N} :) $\endgroup$ – VashTheStampede Aug 7 '18 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.