Solution: XOR Approach
function findMissingCode(codes, n) {
// XOR all numbers from 1 to n
let xorAll = 0;
for (let i = 1; i <= n; i++) {
xorAll ^= i;
}
// XOR all codes in array
let xorArray = 0;
for (const code of codes) {
xorArray ^= code;
}
// Missing number is xorAll XOR xorArray
return xorAll ^ xorArray;
}
// Test
console.log(findMissingCode([1, 2, 4, 5, 6], 6)); // 3
console.log(findMissingCode([1, 2, 3, 5], 5)); // 4
Alternative: Sum Formula
function findMissingCodeSum(codes, n) {
// Expected sum: 1 + 2 + ... + n = n(n+1)/2
const expectedSum = (n * (n + 1)) / 2;
// Actual sum
const actualSum = codes.reduce((sum, code) => sum + code, 0);
return expectedSum - actualSum;
}
console.log(findMissingCodeSum([1, 2, 4, 5, 6], 6)); // 3
Alternative: Hash Set
function findMissingCodeSet(codes, n) {
const set = new Set(codes);
for (let i = 1; i <= n; i++) {
if (!set.has(i)) {
return i;
}
}
return -1; // Not found (shouldn't happen if input valid)
}
console.log(findMissingCodeSet([1, 2, 4, 5, 6], 6)); // 3
Variation: Two Missing Numbers
function findTwoMissing(codes, n) {
// XOR gives us xor of two missing numbers
let xorAll = 0;
for (let i = 1; i <= n; i++) xorAll ^= i;
for (const code of codes) xorAll ^= code;
// xorAll = a ^ b (where a, b are missing)
// Find rightmost set bit
const rightBit = xorAll & -xorAll;
// Partition numbers by this bit
let xor1 = 0, xor2 = 0;
for (let i = 1; i <= n; i++) {
if (i & rightBit) {
xor1 ^= i;
} else {
xor2 ^= i;
}
}
for (const code of codes) {
if (code & rightBit) {
xor1 ^= code;
} else {
xor2 ^= code;
}
}
return [xor1, xor2];
}
console.log(findTwoMissing([1, 2, 5, 6], 6)); // [3, 4] or [4, 3]
Variation: Find Duplicate
function findDuplicate(codes) {
// Array has n+1 elements with values 1 to n
// One value appears twice
// Floyd's cycle detection
let slow = codes[0];
let fast = codes[0];
// Find intersection point
do {
slow = codes[slow];
fast = codes[codes[fast]];
} while (slow !== fast);
// Find entrance to cycle (the duplicate)
slow = codes[0];
while (slow !== fast) {
slow = codes[slow];
fast = codes[fast];
}
return slow;
}
console.log(findDuplicate([1, 3, 4, 2, 2])); // 2
console.log(findDuplicate([3, 1, 3, 4, 2])); // 3
Variation: Missing and Duplicate
function findMissingAndDuplicate(codes, n) {
// One number appears twice, one is missing
// Using XOR
let xor = 0;
for (let i = 1; i <= n; i++) xor ^= i;
for (const code of codes) xor ^= code;
// xor = missing ^ duplicate
const rightBit = xor & -xor;
let xor1 = 0, xor2 = 0;
for (let i = 1; i <= n; i++) {
if (i & rightBit) xor1 ^= i;
else xor2 ^= i;
}
for (const code of codes) {
if (code & rightBit) xor1 ^= code;
else xor2 ^= code;
}
// Determine which is missing and which is duplicate
for (const code of codes) {
if (code === xor1) {
return {duplicate: xor1, missing: xor2};
}
if (code === xor2) {
return {duplicate: xor2, missing: xor1};
}
}
}
console.log(findMissingAndDuplicate([1, 2, 2, 4, 5], 5));
// {duplicate: 2, missing: 3}
Why XOR Works
Properties:
- a ⊕ a = 0
- a ⊕ 0 = a
- Commutative and associative
Example: [1, 2, 4, 5, 6], n=6, missing 3
xorAll = 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6
xorArray = 1 ⊕ 2 ⊕ 4 ⊕ 5 ⊕ 6
xorAll ⊕ xorArray = (1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6) ⊕ (1 ⊕ 2 ⊕ 4 ⊕ 5 ⊕ 6)
= 3 ⊕ (1 ⊕ 1) ⊕ (2 ⊕ 2) ⊕ (4 ⊕ 4) ⊕ (5 ⊕ 5) ⊕ (6 ⊕ 6)
= 3 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0
= 3 ✓
Complexity Comparison
| Approach |
Time |
Space |
Overflow Risk |
| Sum formula |
O(n) |
O(1) |
Yes |
| XOR |
O(n) |
O(1) |
No |
| Hash set |
O(n) |
O(n) |
No |
| Sort + scan |
O(n log n) |
O(1) |
No |
Common Mistakes
- Integer overflow: Sum formula fails for large n
- Modifying array: Some solutions mark visited indices - doesn't work if array is readonly
- Wrong range: Are numbers 0 to n or 1 to n? Clarify!
- Multiple missing: Basic XOR only works for one missing
Follow-Up Questions
Q: What if range is 0 to n instead of 1 to n?
A: Same algorithms work, adjust expected sum
Q: What if array is huge and doesn't fit in memory?
A: Stream through it, XOR or sum still works in one pass
Q: Find missing in unsorted array without extra space?
A: XOR or sum formula
Related Problems
