Definition
- Combined XOR – XOR-ing the entire array gives the XOR of the two unpaired numbers (
x = a ^ b). - Differing bit – since
a != b,xhas at least one set bit; isolate the rightmost withx & (-x). - Partitioning – split every element into two groups by whether the differing bit is set or not.
- Recovery – XOR each group separately; paired values cancel within their group, leaving one single in each.
- Complexity – O(n) time (two passes), O(1) space.
At the National Bank of India, two orphan reconciliation entries slipped through unmatched while everything else is paired. XOR-ing all codes gives the combined fingerprint of the two orphans. Rajesh picks one bit where they differ, sorts every code into two buckets by that bit, and XOR-ing each bucket reveals the orphan in it.
Understanding the Concepts
What is the two single numbers problem?
In an array where every number appears twice except two numbers that each appear once, find both single numbers in O(1) space. This extends the basic single-number XOR trick.
package com.bank.core;
import java.util.Arrays;
public class TwoSingleNumbers {
public static int[] findTwoSingles(int[] nums) {
// Step 1: XOR all to get combined XOR of the two singles
int xor = 0;
for (int n : nums) xor ^= n;
// Step 2: Isolate rightmost set bit
int rightmostBit = xor & (-xor);
// Step 3: Split and XOR each group
int num1 = 0, num2 = 0;
for (int n : nums) {
if ((n & rightmostBit) != 0) {
num1 ^= n;
} else {
num2 ^= n;
}
}
return new int[]{num1, num2};
}
public static void main(String[] args) {
int[] entries = {101, 202, 303, 404, 101, 303};
System.out.println("Two singles: " + Arrays.toString(findTwoSingles(entries)));
}
}
Two singles: [404, 202]
Why does the combined XOR have at least one set bit?
Because the two single numbers are different, their XOR is non-zero. A non-zero XOR means at least one bit position differs between them. That differing bit is the splitter.
package com.bank.core;
public class CombinedXorDemo {
public static void main(String[] args) {
int a = 202, b = 404;
int xor = a ^ b;
System.out.println("202 XOR 404 = " + xor);
System.out.println("Binary: " + Integer.toBinaryString(xor));
System.out.println("Non-zero: differing bits exist");
}
}
202 XOR 404 = 342
Binary: 101010110
Non-zero: differing bits exist
How does x & (-x) isolate the rightmost set bit?
Negating in two's complement flips all bits and adds one. AND-ing the original with its negation keeps only the lowest set bit. Any set bit of the combined XOR would work as the splitter; the rightmost is the cheapest to compute.
package com.bank.core;
public class RightmostBitDemo {
public static void main(String[] args) {
int x = 342; // binary: 101010110
int rightmost = x & (-x);
System.out.println("x = " + x + " binary: " + Integer.toBinaryString(x));
System.out.println("Rightmost set bit: " + rightmost
+ " binary: " + Integer.toBinaryString(rightmost));
}
}
x = 342 binary: 101010110
Rightmost set bit: 2 binary: 10
Why does the split guarantee the two singles land in different groups?
The differing bit is set in exactly one of the two singles and not the other (that is what makes it a differing bit). So one single goes into the "bit set" group and the other into the "bit not set" group. Paired values share the same bit value, so each pair lands in the same group and cancels.
package com.bank.core;
public class SplitGuarantee {
public static void main(String[] args) {
int a = 202, b = 404;
int xor = a ^ b;
int bit = xor & (-xor); // 2
System.out.println("202 & 2 = " + (202 & bit) + " → group " + ((202 & bit) != 0 ? "A" : "B"));
System.out.println("404 & 2 = " + (404 & bit) + " → group " + ((404 & bit) != 0 ? "A" : "B"));
System.out.println("101 & 2 = " + (101 & bit) + " → group " + ((101 & bit) != 0 ? "A" : "B"));
System.out.println("303 & 2 = " + (303 & bit) + " → group " + ((303 & bit) != 0 ? "A" : "B"));
// 101 appears twice in same group → cancels
// 303 appears twice in same group → cancels
}
}
202 & 2 = 2 → group A 404 & 2 = 0 → group B 101 & 2 = 0 → group B 303 & 2 = 2 → group A
What are the edge cases?
Edge cases include the two singles being adjacent and the array having only two elements.
package com.bank.core;
import java.util.Arrays;
public class TwoSinglesEdgeCases {
public static int[] findTwoSingles(int[] nums) {
int xor = 0; for (int n : nums) xor ^= n;
int bit = xor & (-xor);
int a = 0, b = 0;
for (int n : nums) { if ((n & bit) != 0) a ^= n; else b ^= n; }
return new int[]{a, b};
}
public static void main(String[] args) {
System.out.println("Two elements: " + Arrays.toString(findTwoSingles(new int[]{7, 3})));
System.out.println("Adjacent: " + Arrays.toString(findTwoSingles(new int[]{1, 2, 1, 3, 2, 5})));
}
}
Two elements: [7, 3]
Adjacent: [3, 5]
How is this different from the single number problem?
| Aspect | Single Number | Two Single Numbers |
|---|---|---|
| Unpaired elements | 1 | 2 |
| Passes over data | 1 (XOR all) | 2 (XOR all, then split-XOR) |
| Key insight | XOR cancels pairs | Differing bit splits the two singles |
| Extra space | O(1) | O(1) |
| Time | O(n) | O(n) |
What about finding three single numbers?
With three unpaired numbers, the XOR of all elements gives the XOR of all three, which does not directly help. More advanced bit manipulation techniques or mathematical properties of XOR are needed. This is significantly harder and less commonly asked.
What should a senior engineer know?
A senior engineer should explain the distinguishing-bit split clearly: the combined XOR reveals a bit where the two singles differ, and partitioning by that bit separates them. They should know the x & (-x) idiom for isolating the rightmost set bit and understand why each paired value falls into the same group and cancels.
Visual Overview
Array: [101, 202, 303, 404, 101, 303] Step 1: XOR all → 101^202^303^404^101^303 = 202^404 = 342 Step 2: Rightmost set bit of 342 342 = 101010110 -342 = ...complement... 342 & (-342) = 10 = 2 Step 3: Split by bit 2 Group A (bit set): 202(10), 303(10), 303(10) → 202^303^303 = 202 Group B (bit unset): 101(00), 404(00), 101(00) → 101^404^101 = 404 Result: [202, 404] ┌──────────────────────────────────────────┐ │ Combined XOR reveals differing bit │ │ Split → each single in its own group │ │ Pairs cancel within each group │ │ XOR per group → recover each single │ └──────────────────────────────────────────┘
Key Takeaway
Two Single Numbers extends the basic XOR trick to the case where two elements each appear once. XOR-ing the entire array cancels all pairs and leaves the combined XOR of the two singles. Because the two singles are different numbers, this combined value has at least one set bit, and any such bit is a bit where the two singles differ.
Isolate one such bit, conventionally the rightmost using the x & (-x) idiom from two's complement, and use it as a splitter. Pass over the array a second time and route each number into one of two groups depending on whether that bit is set. The two singles are guaranteed to land in different groups, while every paired value still cancels within whichever group it lands in. XOR-ing each group independently reveals the two singles.
At the National Bank of India, Rajesh uses this when two reconciliation entries, rather than one, are left unmatched while everything else is paired. XOR-ing all codes gives their combined fingerprint, isolating a differing bit partitions the codes into two buckets, and each orphan is revealed by XOR. The whole operation takes O(n) time and O(1) space.
The key interview insight is the distinguishing-bit split. The x & (-x) idiom isolates the rightmost set bit, and understanding why it works requires knowing two's complement. Being able to explain the split, the pairing guarantee, and the rightmost-bit idiom shows bit-level reasoning under a space constraint.
Remember one sentence: XOR everything to combine the two singles, isolate a differing bit to split them into separate groups, and XOR each group to recover each single.
---