Pattern visualizer
Count Pairs With Given XOR
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. 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..
Each element computes the partner it needs, a map counts how many are behind it
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.
1FUNCTION countPairsWithXor(nums, x)2 count <- 03 seen <- EMPTY MAP4 FOR j <- 0 TO LENGTH(nums) - 15 need <- nums[j] XOR x6 IF need IN seen7 count <- count + seen[need]8 seen[nums[j]] <- seen[nums[j]] + 19 RETURN count
← / → step · space play · Home restart