XOR Pairs
Practice
4.6 (9 votes)
Bit manipulation
Basics of bit manipulation
Basic programming
Problem
71% Success 1871 Attempts 10 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You are given an array \(A\) of \(N\) non-negative integers. Find the number of pairs of indices \((i,\ j)\) \((1 \le i < j \le N)\), such that \(A[i] \oplus j = A[j] \oplus i\), where \(\oplus\) is the bitwise XOR operator.

Input format

The first line contains a single integer \(T\) denoting the number of test cases.

For each test case, the first line contains a single integer \(N\) denoting the size of the array \(A\). The next line contains \(N\) space-seperated integers denoting the elements of the array.

Output format

The output must contain a single integer, that is the number of pairs described in the statement.

Constraints

\(1 \le T \le 10\)

\(1 \le N \le 2 \times 10^5\)

\(0 \le A[i] \le 10^9\)

It is guaranteed that the sum of \(N\) does not exceed \(2 \times 10^5\) over all test cases.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:10
87 votes
Tags:
Basic ProgrammingBit ManipulationC++
Points:10
80 votes
Tags:
Bit manipulationBit ManipulationBasics of Bit ManipulationBasic Programming
Points:10
8 votes
Tags:
ImplementationBasics of Bit ManipulationBasic ProgrammingBit ManipulationBit manipulation