The missing trade sequence number

Question

A gap-free feed should deliver sequence numbers 1 through n, but exactly one is missing, so you receive n - 1 distinct numbers in some order. Find the missing one.

seqs = [1, 2, 4, 5], n = 5
-> 3

Return the missing number. Aim for $O(n)$ time and $O(1)$ space.

Accepted Answer

The sum of 1 through n is n(n + 1) / 2. Subtract the sum of what you actually received; the difference is exactly the missing number. No sorting or auxiliary set needed. Tracing [1, 2, 4, 5] with n = 5: the full sum is 15, the received sum is 12, and 15 - 12 = 3. Time O(n), space O(1). The closed-form sum is exact for integers. If overflow were a concern in a fixed-width language, XOR-ing all values with 1..n finds the missing number without ever forming a large sum, a useful variant to mention. Takeaway. An invariant of the complete set (its sum, or its XOR) minus the same invariant of the r…

The missing trade sequence number

Your answer

More Coding questions