Count Pairs With Given XOR
A medium Bit Manipulation problem included in Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Bit Manipulation
- Sheets
- 2
- Core for
- 9 roles
- Platform
- GeeksforGeeks
The problem
Given an array of integers and a target value, return the number of pairs (i, j) where i < j and arr[i] XOR arr[j] equals the target.
Example 1
- Input
- arr = [5, 4, 7, 2, 2], target = 6
- Output
- 2
- Why
- Pairs with XOR 6: indices (1,3) where 4^2=6, and (1,4) where 4^2=6. Total count is 2.
Example 2
- Input
- arr = [1, 2, 3, 4, 5, 6], target = 7
- Output
- 3
- Why
- Pairs with XOR 7: (1,6), (2,5), (3,4). At indices: arr[0]^arr[5]=1^6=7, arr[1]^arr[4]=2^5=7, arr[2]^arr[3]=3^4=7. Total count is 3.
Constraints
- 1 <= arr.length <= 10^5
- 0 <= arr[i] <= 10^5
- 0 <= target <= 10^5
How to think about it
Updated 2026-09-09The identity a ^ b = target is algebraically equivalent to b = a ^ target by XORing a on both sides. This reframes the problem from searching across all pairs to checking if a specific companion value was already seen. Every element looks for exactly one complement.
Approaches, worst first
Nested pair scan
time O(n^2) · space O(1)
Evaluate arr[i] ^ arr[j] for every combination of indices with i < j. Requires no extra memory, but comparing all pairs is completely infeasible on arrays of size 10^5.
Frequency table lookupWrite this one
time O(n) · space O(u)
Maintain a frequency map or array of seen values. For each number x, add the frequency of x ^ target to the total answer, then increment the frequency of x. Visiting left to right strictly counts pairs with i < j without double counting.
Where people lose marks · 3
- Populating the entire frequency map before querying pairs counts every pair twice and miscounts self-pairs when target is 0 unless careful division and adjustments are made.
- Sizing a direct frequency array based only on the maximum value in arr; x ^ target can exceed max(arr), so the frequency buffer must accommodate values up to max(x ^ target) or use a hash map.
- Integer overflow of the pair count: on an array of 10^5 identical elements with target 0, the number of valid pairs is roughly 5 * 10^9, exceeding 32-bit signed integers.
The theory behind it
Bit Manipulation — the ground this problem stands on. All Bit Manipulation problems
What Bit Manipulation is
Bit manipulation is the practice of working directly on the individual ones and zeros that form numbers in computer memory. Every integer is stored as a tiny row of electrical switches that are either on or off. Instead of running arithmetic loops, bitwise operations flip, mask, shift, or combine these switches in a single hardware cycle. This allows compact storage of sets and blazing-fast checks without allocating extra memory.
When to reach for it
Reach for bit manipulation when problems ask to find a unique non-duplicate number, count set bits, determine if a value is a power of two, or pack a set of small booleans into a single integer. Prompts mentioning constant O(1) auxiliary space constraints on array queries often hint at XOR cancellation. It is also the foundation of bitmask dynamic programming, where subsets of up to twenty items are tracked as integer masks.
How the pattern works
Think of an integer as a fixed-length set of flags. Use bitwise AND to inspect if a specific bit is set, bitwise OR to turn a bit on, and bitwise XOR to flip a bit or cancel out matched pairs. Learn the standard bit tricks: n AND with n minus one clears the lowest set bit, which counts ones quickly, while n AND with negative n isolates the lowest set bit. When packing sets into masks, represent the empty set as zero and add item i by shifting one left by i and combining with OR.
What each operation costs
| Operation | Time |
|---|---|
| bitwise operation like AND, OR, or XOR | O(1) |
| count set bits across fixed integer width | O(1) |
| find single non-duplicate number using XOR | O(n) |
What usually goes wrong with Bit Manipulation
- Forgetting that bitwise operators have lower operator precedence than equality and arithmetic comparisons in most languages, evaluating expressions in the wrong order without parentheses.
- Using signed right shift instead of unsigned logical right shift when processing negative numbers, which fills high-order bits with ones instead of zeros.
- Shifting bits by thirty-two or more on standard 32-bit integers, causing undefined behavior or wrapped bit shifts that yield incorrect masks.
Which roles need this problem
Bit Manipulation is a core topic for these 9 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 2 more roles, including ML Engineer, Information Retrieval Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Bit Manipulation problems
Problem set and role mapping as of .