Given an array A consist of N integers (N <= 100000, 0 <= Ai <= sqrt(i) for 1 <= i <= N). Count the number of triple (i, j, k) such that i <= j <= k and (Ai xor Aj xor Ak) = 0.
I tried many approaches but I couldn't optimize my O(N^2) solution. Is there any efficient algorithm to solve this problem?
We can improve complexity to due to
Unable to parse markup [type=CF_TEX]
. Calculate frequencies of the elements while going from left to right, considering the Ak element in the triple. Now, we need to find the number of pairs i, j such thatUnable to parse markup [type=CF_TEX]
. Now, in time we can traverse the frequencies, considering element Aj, assumingUnable to parse markup [type=CF_TEX]
, and addingUnable to parse markup [type=CF_TEX]
for Ai < Aj (that way we will count each pair once). Case ofUnable to parse markup [type=CF_TEX]
should be handled separately —Unable to parse markup [type=CF_TEX]
. The actual running time will be slightly better than since we don't traverse all the frequencies every iteration.