How do you find the missing number in an array containing 1 to n?
Short answer: An array holds n - 1 distinct numbers from 1 to n with one missing. Compute the expected sum n(n+1)/2 and subtract every element; what is left is the missing number. XOR-ing gives the same answer without any risk of overflow.
#include <stddef.h>
/* arr has n-1 elements, values 1..n with one missing */
unsigned missing_sum(const unsigned *arr, unsigned n)
{
unsigned long long total = (unsigned long long)n * (n + 1) / 2;
for (unsigned i = 0; i < n - 1; i++)
total -= arr[i];
return (unsigned)total;
}
unsigned missing_xor(const unsigned *arr, unsigned n)
{
unsigned x = 0;
for (unsigned i = 1; i <= n; i++) x ^= i; /* XOR of 1..n */
for (unsigned i = 0; i < n - 1; i++) x ^= arr[i]; /* cancel present ones */
return x;
}
/* {1, 2, 4, 5, 6}, n = 6 -> 3 */
Dry run (sum method): n = 6, expected sum 21. Elements sum to 1+2+4+5+6 = 18. 21 - 18 = 3.
Watch the length. A common version is findMissingNumber(arr, n) with the loop running i < n. That only works if n is the array length and the range is 1..n+1. Be explicit about which n you mean: "the array has n−1 elements and the numbers run from 1 to n".
Overflow: n * (n + 1) overflows a 32-bit int once n passes about 46,000. Widening to 64-bit, subtracting as you go, or using XOR all avoid it. With XOR every value stays in range because XOR never grows the number.
Complexity: O(n) time, O(1) extra space. Sorting first would be O(n log n); a "seen" array would use O(n) memory.
Follow-ups
- Two numbers missing: XOR gives
a ^ b; split by any set bit (as in "two unique numbers") to separate them. Or use both the sum and the sum of squares. - Array not guaranteed valid (duplicates possible): use the cyclic-sort idea (place each value
vat indexv-1) or a bitmap.