A high-security archive protects each vault with a numeric access code. Auditors want to know how many ways they can select three distinct vaults, at three distinct positions in the ledger, such that XOR-combining their codes produces a reading whose binary representation has an even number of set (1) bits. Such a selection is called a balanced triad.
You are given the vault codes in their fixed ledger order. Count the number of balanced triads, where a triad is chosen by picking three positions i < j < k from the ledger (two triads are different if the set of chosen positions differs, even when the underlying code values happen to be equal).
n, the number of vaults.n space-separated integers, the codes of the vaults in ledger order.A single integer: the number of index triples (i, j, k) with i < j < k such that code[i] XOR code[j] XOR code[k] has an even number of 1 bits in its binary representation.
3 <= n <= 2000 <= code[i] <= 10^9Example 1
Input
4 1 2 3 4
Expected
3
Explanation
The vault codes are 1, 2, 3, 4. Checking all four triples of positions: (1,2,3) gives 1^2^3=0 (zero set bits, even); (1,2,4) gives 1^2^4=7=111b (three set bits, odd); (1,3,4) gives 1^3^4=6=110b (two set bits, even); (2,3,4) gives 2^3^4=5=101b (two set bits, even). Three of the four triples are balanced, so the answer is 3.
Example 2
Input
3 0 0 0
Expected
1
Explanation
There is only one possible triad, using all three vaults. Its XOR is 0^0^0=0, which has zero set bits (even), so it is balanced. The answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →