XOR Master

TarifEzaz BRACU Intra Programming C...

If we use bit-wise exclusive-or operators that are available in most of the languages and compare all the pairs using nested loops, it would take O(N2) to solve the problem. Since for this problem N <= 105, we need an asymptotically faster solution.

The first thing to notice in this problem is that the exclusive-or between two numbers is 0, only when both of the numbers have the same value. Otherwise, the exclusive-or between two numbers will be a non-zero value. If all the numbers of a given testcase are distinct, then the answer will be NC2 or ( N * ( N - 1 ) ) / 2. Now, imagine a number x has occurred p times in the sequence. If we pick any two x's from the p available options, the result will be 0. So, there are ( p * ( p - 1 ) ) / 2 ways to select such pairs of x. These pairs should be subtracted from the total number of possible pairs. For C++ coders, the frequencies of given numbers can be calculated using maps. This would result in an O( NlgN ) expected solution.


81% Solution Ratio
Bishal_GEarliest, Jan '17
ajudge.bdFastest, 0.0s
ajudge.bdLightest, 5.5 kB
mdvirusShortest, 258B
Toph uses cookies. By continuing you agree to our Cookie Policy.