Find the Missing Number in a Sequence

An array of n distinct integers is formed by taking all values in the range [0, n] except exactly one, then arranging the remaining n values in arbitrary order. Determine the single missing value using an O(n) search/aggregation technique, such as comparing the expected sum of 0..n against the array's actual sum.

Input: The first line contains the integer n (the number of elements in the array). The second line contains n space-separated integers drawn from [0, n], missing exactly one value. Output: Print a single integer: the missing value.

1 <= n <= 10^5 0 <= a[i] <= n All a[i] are distinct.

Using a 64-bit accumulator for the sums (even though individual values are small) is a sensible precaution - though for n up to 10^5 here, the sums stay well within normal integer range, this habit matters more as constraints grow.

Find the one missing value from an array that should contain every integer from 0 to n except one. Brute force: Sort the array and scan for the first index where the value doesn't match its expected position - this works but costs O(n log n) for the sort, when the sum-difference trick achieves the same result in O(n). Optimised: Since the array is GUARANTEED to be the full range [0,n] minus exactly one value, the DIFFERENCE between the known closed-form expected sum and the array's actual computed sum directly isolates the missing value - no sorting or searching needed at all, just two sums and a subtraction.

1. Compute the EXPECTED sum of the full range [0, n] using the closed-form formula n*(n+1)/2 - this is O(1), no loop needed. 2. Compute the ACTUAL sum of the given array's values. 3. The DIFFERENCE between the expected sum and the actual sum is exactly the missing value.

Time: O(n) - one pass to compute the actual sum (the expected sum is O(1) via the formula). Space: O(1) - just a couple of accumulator variables.

The missing value can be 0 or n itself (the smallest or largest possible value); n = 1 leaves an array with a single element from {0, 1}.

Be ready to mention the XOR-based alternative (XOR-ing every value from 0 to n together with every array element - the missing value is what survives, since everything else cancels out in pairs) as another elegant O(n) time, O(1) space technique, avoiding any overflow concerns the sum-based approach might have for very large n.