Exploring the Missing Number in Array Problem

Quick answer: Given an array of N−1 distinct integers from the range 1 to N, the missing number is simply the sum of 1 to N minus the sum of the array: N*(N+1)/2 − sum(arr). That runs in O(N) time and O(1) extra space. A sort-and-scan approach also works but costs O(N log N), and an XOR trick gives the same O(N) result without any risk of integer overflow.

“Missing Number in Array” is one of the first problems most people meet on GeeksforGeeks, LeetCode (problem 268) and in campus placement rounds. It looks trivial, yet interviewers love it because it separates candidates who reach for brute force from those who spot the mathematical shortcut. In this guide we walk through the problem statement, two worked examples, three solutions with increasing elegance, a complexity comparison, and complete working code in both Python and C++.

Problem statement

You are given an array A of size N−1 containing distinct integers in the range 1 to N. Exactly one number from that range is absent. Return the missing number.

Constraints you can assume in the classic version: 1 ≤ N ≤ 10⁶, every element is unique, and there is exactly one missing value.

Example 1

Input: N = 7, A = {1, 2, 3, 4, 5, 7}
Output: 6
Every integer from 1 to 7 appears except 6.

Example 2

Input: N = 10, A = {1, 3, 10, 5, 4, 6, 7, 9, 8}
Output: 2
The array is unsorted and 2 is the only value from 1 to 10 that never shows up.

Approach 1: Sort and scan

The most natural idea is to put the numbers in order and look for the first gap.

1. Sort the array in non-decreasing order.
2. Keep a counter expected starting at 1.
3. Walk through the array. If A[i] == expected, increment expected. Otherwise expected is the missing number.
4. If the loop finishes without a mismatch, the missing number is N (it was the last one).

Dry run on Example 2: sorted array is {1, 3, 4, 5, 6, 7, 8, 9, 10}. expected = 1 matches A[0] = 1, so expected becomes 2. A[1] = 3 ≠ 2, so we return 2.

Sorting dominates the cost at O(N log N). The scan is O(N). Note that the original version of this solution forgot the “missing number is N” case — if A = {1, 2, 3} and N = 4, the loop ends without returning, which is undefined behaviour in C++. Always handle that edge.

Approach 2: Sum formula (optimal)

Gauss showed that the sum of the first N natural numbers is N × (N + 1) / 2. If we know what the total should be and we know what is actually there, the difference is the missing number.

1. Compute total = N * (N + 1) / 2.
2. Subtract every element of the array from total.
3. Whatever remains is the answer.

Dry run on Example 2: total = 10 × 11 / 2 = 55. Array sum = 1 + 3 + 10 + 5 + 4 + 6 + 7 + 9 + 8 = 53. Missing = 55 − 53 = 2.

One pass over the array, no sorting, no extra memory: O(N) time and O(1) space. The only caveat is overflow. For N up to 10⁶, N*(N+1)/2 is about 5 × 10¹¹, which does not fit in a 32-bit int. Use long long in C++ or Java’s long. Python integers are arbitrary precision, so this is not an issue there.

Approach 3: XOR trick (optimal, overflow-free)

XOR has two useful properties: x ^ x = 0 and x ^ 0 = x. If you XOR all numbers from 1 to N together, then XOR all elements of the array into the same accumulator, every number that appears in both cancels out. The single survivor is the missing number.

Same O(N) time and O(1) space as the sum approach, with no overflow concern because XOR never grows beyond the bit width of the inputs. It is a favourite follow-up question in interviews: “Can you do it without the sum formula?”

Complexity comparison

Working code in Python

All three approaches, each as a separate function, tested against both examples:

def missing_sort_scan(arr: list[int], n: int) -> int:
    arr = sorted(arr)
    expected = 1
    for value in arr:
        if value != expected:
            return expected
        expected += 1
    return n  # the last number was the missing one


def missing_sum(arr: list[int], n: int) -> int:
    total = n * (n + 1) // 2
    return total - sum(arr)


def missing_xor(arr: list[int], n: int) -> int:
    acc = 0
    for i in range(1, n + 1):
        acc ^= i
    for value in arr:
        acc ^= value
    return acc


if __name__ == "__main__":
    tests = [
        (7,  [1, 2, 3, 4, 5, 7]),
        (10, [1, 3, 10, 5, 4, 6, 7, 9, 8]),
        (4,  [1, 2, 3]),          # edge case: N itself is missing
    ]
    for n, arr in tests:
        print(missing_sort_scan(arr, n), missing_sum(arr, n), missing_xor(arr, n))

Output:

6 6 6
2 2 2
4 4 4

Working code in C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Approach 1: sort and scan, O(N log N)
    int missingSortScan(vector<int> arr, int n) {
        sort(arr.begin(), arr.end());
        int expected = 1;
        for (int value : arr) {
            if (value != expected) return expected;
            expected++;
        }
        return n;  // N was the missing number
    }

    // Approach 2: sum formula, O(N). long long avoids overflow for large N.
    int missingSum(const vector<int>& arr, int n) {
        long long total = 1LL * n * (n + 1) / 2;
        for (int value : arr) total -= value;
        return static_cast<int>(total);
    }

    // Approach 3: XOR, O(N), no overflow
    int missingXor(const vector<int>& arr, int n) {
        int acc = 0;
        for (int i = 1; i <= n; i++) acc ^= i;
        for (int value : arr) acc ^= value;
        return acc;
    }
};

int main() {
    Solution sol;
    vector<int> a1 = {1, 2, 3, 4, 5, 7};
    vector<int> a2 = {1, 3, 10, 5, 4, 6, 7, 9, 8};

    cout << "Example 1: " << sol.missingSum(a1, 7)  << " "
         << sol.missingXor(a1, 7) << " " << sol.missingSortScan(a1, 7) << endl;   // 6 6 6
    cout << "Example 2: " << sol.missingSum(a2, 10) << " "
         << sol.missingXor(a2, 10) << " " << sol.missingSortScan(a2, 10) << endl; // 2 2 2
    return 0;
}

Once you are comfortable here, the natural next problem is finding the second largest element in an array, which uses the same single-pass thinking with a slightly trickier state to track.

Common mistakes and pitfalls

1. Integer overflow in the sum formula. n * (n + 1) overflows a 32-bit int once N exceeds roughly 46,000. Use long long (C++) or long (Java), or switch to XOR.
2. Forgetting that N itself can be missing. In the sort-and-scan approach the loop ends without a mismatch; you must return N after the loop.
3. Confusing array size with N. The array has N−1 elements. If a platform passes you only the array, N is len(arr) + 1.
4. Assuming 0-based range. LeetCode 268 uses the range 0 to N with N elements; GeeksforGeeks uses 1 to N with N−1 elements. Read the statement; the formula adjusts but the idea is identical.
5. Sorting when you do not need to. Sorting is the right first instinct but a poor final answer; always ask yourself whether a single pass can do the job.
6. Not testing the edge cases. Try N = 1 (empty array, answer 1), the missing number at the start, and the missing number at the end before you submit.

Frequently asked questions

What if the array can contain duplicates?

Then the sum and XOR tricks break, because the problem is no longer “one missing number”. You would use a hash set or a boolean marker array to record which values are present, then scan 1 to N for the absent one. That is O(N) time and O(N) space.

What if two numbers are missing?

Use both the sum and the sum of squares to form two equations in two unknowns, or partition by an XOR bit. The two-missing-numbers variant is a common follow-up in product-company interviews.

Why is the sum formula O(1) space when the sort approach is not?

The sum approach stores only one accumulator regardless of N. Sorting may need O(log N) stack space (quicksort) or O(N) buffer space (merge sort, and Python’s sorted() creates a new list).

Which solution should I give in an interview?

Mention sort-and-scan in one sentence to show you considered it, then present the sum formula as your answer, call out the overflow risk, and offer XOR as the fix. That sequence demonstrates exactly the reasoning interviewers want to see.

Key takeaways

• The missing number equals N*(N+1)/2 − sum(arr): one pass, constant memory.
• Sort-and-scan works but costs O(N log N) and has an easy-to-miss edge case when N is the missing value.
• XOR gives the same O(N) result with zero overflow risk and is the standard follow-up answer.
• Always use 64-bit integers for the sum in C++ and Java when N can be large.
• Test the three edges: missing at the start, missing at the end, and N = 1.

Problems like this are the warm-up round of most technical interviews. If you want a structured path through arrays, strings, recursion, dynamic programming and system design — with mock interviews and mentor feedback — explore our Interview Preparation program. Prefer video walkthroughs? Follow along on our YouTube channel.