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.

82%
Solution Ratio

Bishal_GEarliest,

tuhin107494Fastest, 0.0s

sajjad_99Lightest, 262 kB

mdvirusShortest, 258B

Toph uses cookies. By continuing you agree to our Cookie Policy.