</>EmbeddedInterview

How do you find the missing number in an array containing 1 to n?

EasyArrays & Strings (Coding Round)

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 v at index v-1) or a bitmap.