DSA Tracker

Visualize

Count all pairs with given XOR

Each element computes the partner it needs, a map counts how many are behind it

time O(n)space O(n)

XOR undoes itself, and that turns a search into a lookup. If nums[i] XOR nums[j] = x, then XORing both sides by nums[j] gives nums[i] = nums[j] XOR x — so an element does not have to hunt for a partner, it can compute the partner's exact value. Sweep left to right keeping a map from value to how many times it has been seen. At each element, add the stored count of nums[j] XOR x, then record nums[j] itself. Storing counts rather than a plain set is what handles duplicates: if the needed value sits at three earlier positions, that element closes three pairs, not one. Every pair is tallied once, at its right-hand element, so ordering takes care of itself.

Details

Animated on: nums = [3,6,8,15,6,5,3,10], x = 5 — count the pairs i < j with nums[i] XOR nums[j] = x.

Problem:Count all pairs with given XORMedium

Each element computes the partner it needs, a map counts how many are behind it

step 1 / 10

3
[0]
6
[1]
8
[2]
15
[3]
6
[4]
5
[5]
3
[6]
10
[7]

Looking for pairs whose XOR is 5. Testing every pair costs 28 comparisons here, but XOR is its own inverse: if a XOR b = 5 then b = a XOR 5. So each element already knows the exact value of the partner it needs, and the only question left is how many of those partners lie behind it.

Pseudocode
1FUNCTION countPairsWithXor(nums, x)
2  count <- 0
3  seen <- EMPTY MAP
4  FOR j <- 0 TO LENGTH(nums) - 1
5    need <- nums[j] XOR x
6    IF need IN seen
7      count <- count + seen[need]
8    seen[nums[j]] <- seen[nums[j]] + 1
9  RETURN count

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. Looking for pairs whose XOR is 5. Testing every pair costs 28 comparisons here, but XOR is its own inverse: if a XOR b = 5 then b = a XOR 5. So each element already knows the exact value of the partner it needs, and the only question left is how many of those partners lie behind it.
  2. nums[0] = 3 needs a partner equal to 3 XOR 5 = 6, but 6 has not appeared anywhere to its left, so this element closes no pair and the count stays 0. It is still filed away, because a later element may turn out to need 3 as its own partner.
  3. nums[1] = 6 needs a partner equal to 6 XOR 5 = 3, and 3 has already been seen 1 time — at index 0 (3 XOR 6 = 5). Each of those earlier cells forms its own valid pair with this one, so the count jumps by 1 to 1. Counting occurrences rather than just asking "does 3 exist" is what makes duplicates come out right.
  4. nums[2] = 8 needs a partner equal to 8 XOR 5 = 13, but 13 has not appeared anywhere to its left, so this element closes no pair and the count stays 1. It is still filed away, because a later element may turn out to need 8 as its own partner.
  5. nums[3] = 15 needs a partner equal to 15 XOR 5 = 10, but 10 has not appeared anywhere to its left, so this element closes no pair and the count stays 1. It is still filed away, because a later element may turn out to need 15 as its own partner.
  6. nums[4] = 6 needs a partner equal to 6 XOR 5 = 3, and 3 has already been seen 1 time — at index 0 (3 XOR 6 = 5). Each of those earlier cells forms its own valid pair with this one, so the count jumps by 1 to 2. Counting occurrences rather than just asking "does 3 exist" is what makes duplicates come out right.
  7. nums[5] = 5 needs a partner equal to 5 XOR 5 = 0, but 0 has not appeared anywhere to its left, so this element closes no pair and the count stays 2. It is still filed away, because a later element may turn out to need 5 as its own partner.
  8. nums[6] = 3 needs a partner equal to 3 XOR 5 = 6, and 6 has already been seen 2 times — at index 1 (6 XOR 3 = 5) and index 4 (6 XOR 3 = 5). Each of those earlier cells forms its own valid pair with this one, so the count jumps by 2 to 4. Counting occurrences rather than just asking "does 6 exist" is what makes duplicates come out right.
  9. nums[7] = 10 needs a partner equal to 10 XOR 5 = 15, and 15 has already been seen 1 time — at index 3 (15 XOR 10 = 5). Each of those earlier cells forms its own valid pair with this one, so the count jumps by 1 to 5. Counting occurrences rather than just asking "does 15 exist" is what makes duplicates come out right.
  10. Every element was asked exactly once who its partner would have to be, and the map answered how many were already behind it — 5 pairs in total. Each pair is counted once, at its RIGHT-hand element, which is why nothing is double counted and no ordering check is needed.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count all pairs with given XOR in the editorAll Bit Manipulation problemsBack to roadmap