Q6: How do you find the single missing number in an array containing numbers 0 to n?
Use Gauss's Sum Formula: expected sum $S = frac{n(n + 1)}{2}$. Calculate the actual sum of array elements and subtract it from $S$. Alternatively, use XOR: $x oplus x = 0$, XORing indices and values leaves the missing number.
XOR Solution for Missing Number
public class MissingNumber {
public static int findMissing(int[] nums) {
int xor = nums.length;
for (int i = 0; i < nums.length; i++) {
xor ^= i ^ nums[i];
}
return xor;
}
}💡 XORing all indices and array values cancels out duplicate pairs, leaving the missing number.
Key Takeaways
- Mathematical approach: $ ext{Expected Sum} - ext{Actual Sum} = ext{Missing Number}$.
- XOR approach avoids potential integer overflow errors.
Knowledge Check
What primary advantage does the Bitwise XOR method have over Gauss's sum formula when n is very large?