Beginner LevelData Structures & Algorithms
How do you find a Missing Number using XOR or Gauss's formula?
ā Interview Prompt: Find the missing number in an array of [0..N] in O(N) time and O(1) space using XOR bit tricks or the arithmetic sum formula.
Given array of $N$ distinct integers in range $[0, N]$ with one missing:
Approach 1: Gauss Formula ā $O(N)$ time, $O(1)$ space
Expected sum $= N(N+1)/2$. Missing = expected ā actual sum.
Approach 2: XOR ā $O(N)$ time, $O(1)$ space
XOR all numbers $0..N$ with all array elements. Paired duplicates cancel ($x \oplus x = 0$); remaining value = missing number.
ā¢
XOR approach avoids potential integer overflow with large $N$ (though JavaScript uses BigInt or 64-bit float).
Code Implementation Example
typescript
// Gauss formula approach
function missingNumberGauss(nums: number[]): number {
const n = nums.length;
const expected = (n * (n + 1)) / 2;
return expected - nums.reduce((s, v) => s + v, 0);
}
// XOR approach
function missingNumberXOR(nums: number[]): number {
let xor = nums.length; // XOR with n first
for (let i = 0; i < nums.length; i++) {
xor ^= i ^ nums[i]; // XOR index and value
}
return xor;
}
console.log(missingNumberXOR([3, 0, 1])); // 2š”Missing number found in O(N)/O(1) using Gauss formula and XOR.
šÆ Interview Key Takeaway
XOR cancellation (aāa=0, aā0=a) is an O(1) space trick for finding unique/missing elements. Know both XOR and sum approaches.
#DSA#XOR#Bit Manipulation#Arrays#Beginner
Back to all Data Structures & Algorithms Questionsā