Finding the Missing Number — What I Tried vs What I Learned About Optimal Patterns

#dsa #programming #cpp #beginners

When solving the Missing Number problem, I didn’t jump to the optimal solution immediately.
Instead, I used the patterns I had already learned — and that’s exactly how learning should work.

This article documents:

what I tried
why it’s correct
why it’s not optimal
what I learned next

Problem Summary

Given an array of size n containing numbers from 1 to n+1
(with exactly one number missing), find the missing number.

What I Tried — Sorting Approach

Idea

If the array is sorted, the missing number is the first place where
index + 1 != value.

Code

sort(arr.begin(), arr.end());
for(int i = 0; i < arr.size(); i++) {
    if(arr[i] != i + 1)
        return i + 1;
}
return arr[arr.size() - 1] + 1;

Analysis

✔️ Correct logic
Time complexity: O(n log n)
Sorting is unnecessary

What I Tried — Frequency Count

Idea

If I count occurrences, the number with frequency 0 is missing.

Code (simplified)

int maxNum = 0;
for(int x : arr) maxNum = max(maxNum, x);

vector<int> freq(maxNum + 1, 0);
for(int x : arr) freq[x]++;

for(int i = 1; i < freq.size(); i++) {
    if(freq[i] == 0)
        return i;
}

Analysis

✔️ Correct
Time: O(n)
Space: O(n) extra memory

What I Learned — Optimal Pattern (Math / XOR)

Key Insight

This problem does not need sorting or frequency.We already know the expected numbers.

Sum Formula Approach

int missingNum(vector<int>& arr) {
    int n = arr.size();
    long long expected = 1LL * (n + 1) * (n + 2) / 2;
    long long actual = 0;

    for(int x : arr) actual += x;
    return expected - actual;
}

Time: O(n)
Space: O(1)

Note:1LL ensures the multiplication happens in long long to avoid overflow.

XOR Approach (Best)

int missingNum(vector<int>& arr) {
    int n = arr.size();
    int ans = 0;

    for(int i = 1; i <= n + 1; i++) ans ^= i;
    for(int x : arr) ans ^= x;

    return ans;
}

Time: O(n)
Space: O(1)

No overflow risk

What I Learned

My pattern recognition was correct. I used the patterns I knew (sorting, frequency). The problem had a better pattern I hadn’t learned yet. Learning optimal solutions comes after learning more patterns