| # | User | Rating |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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 
. 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 that 
. Now, in 
time we can traverse the frequencies, considering element Aj, assuming 
, and adding freqAj × freqAi for Ai < Aj (that way we will count each pair once). Case of Ak = 0 should be handled separately — 
. The actual running time will be slightly better than 
since we don't traverse all the frequencies every iteration.