Why is XOR useful for finding the missing number?

Every value present in both the expected range and the array appears twice in the combined XOR and cancels because x ^ x = 0. Only the missing value appears once and remains.

Which is preferable: the mathematical sum or XOR approach?

Both use O(N) time and O(1) auxiliary space. The sum approach is simpler mathematically, while XOR avoids the possibility of overflowing an intermediate arithmetic sum when fixed-width integer types are used.

Does the array need to be sorted for the Sum or XOR approach?

No. Addition and XOR are independent of element order, so both approaches work on an unsorted array.

Would these approaches work if more than one number were missing?

Not directly. Both rely on exactly one value being absent. Multiple missing values require a different technique depending on the problem constraints.

Why is the distinct-elements condition important?

The cancellation and expected-range logic assume that every present number occurs exactly once. Duplicate values would break that one-to-one relationship.

Missing Number | takeUforward

Given an array nums containing n distinct integers taken from the range 0 to n, return the single number from this range that is missing from the array.

Example 1

Input: nums = [3, 0, 1]

Output: 2

Explanation:
The complete range is from 0 to 3: [0, 1, 2, 3].
The number 2 is missing from the array.

Example 2

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]

Output: 8

Explanation:
The complete range is from 0 to 9.
Every number is present except 8.

Brute Force Approach

Since the array contains every value from 0 to n except one, sorting places the existing values in their expected order.

After sorting, the value at index i should normally be i. Therefore, the first index where nums[i] != i identifies the missing number. If every index matches, then all values from 0 to n - 1 are present, so n must be missing.

Algorithm

Store the size of nums in n, which also represents the largest possible value in the expected range.
Sort nums in ascending order so each present value can be compared with its expected index.
Traverse indices from 0 to n - 1.
If nums[i] != i, return i because that expected value is missing from the sorted sequence.
If no mismatch is found, return n because all values from 0 to n - 1 are present.

Dry Run

Missing Number Brute Force Approach Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
6    int missingNumber(vector<int>& nums) {
7        int n = nums.size();
8
9        /*
10         * Sorting places each present value near its expected
11         * index, so the first mismatch reveals the missing value.
12         */
13        sort(nums.begin(), nums.end());
14
15        for (int i = 0; i < n; i++) {
16            if (nums[i] != i) {
17                return i;
18            }
19        }
20
21        /*
22         * If every index from 0 to n - 1 matches,
23         * the only missing value from the range is n.
24         */
25        return n;
26    }
27};
28
29int main() {
30    vector<int> nums = {3, 0, 1};
31
32    Solution solution;
33    cout << solution.missingNumber(nums) << endl;
34
35    return 0;
36}

Complexity Analysis

Time Complexity: O(N log N), because sorting dominates the O(N) traversal.

Space Complexity: Depends on the sorting implementation. An in-place sort may use only auxiliary stack space, while some language/library sorting algorithms may require additional memory.

Better Approach

The complete range 0 to n has a known total sum:

n * (n + 1) / 2

Since nums contains every value from that range except one, subtracting the actual array sum from the expected sum directly gives the missing number.

This removes the need for sorting and reduces the time complexity to linear time.

Algorithm

Store the size of nums in n, because the complete expected range is 0 through n.
Compute the expected sum of this range using n * (n + 1) / 2.
Initialize actualSum = 0 to accumulate the values present in the array.
Traverse nums and add every element to actualSum.
Return expectedSum - actualSum, because the difference is the only value absent from the array.

Dry Run

Missing Number Better Approach Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
6    int missingNumber(vector<int>& nums) {
7        long long n = nums.size();
8
9        /*
10         * Use a wider integer type because n * (n + 1)
11         * may exceed the range of a regular int.
12         */
13        long long expectedSum = n * (n + 1) / 2;
14        long long actualSum = 0;
15
16        for (int value : nums) {
17            actualSum += value;
18        }
19
20        /*
21         * Every expected value except the missing one
22         * appears in actualSum, so the difference is the answer.
23         */
24        return static_cast<int>(expectedSum - actualSum);
25    }
26};
27
28int main() {
29    vector<int> nums = {3, 0, 1};
30
31    Solution solution;
32    cout << solution.missingNumber(nums) << endl;
33
34    return 0;
35}

Complexity Analysis

Time Complexity: O(N), because the array is traversed once.

Space Complexity: O(1), because only a few variables are used.

Optimal Approach

XOR is useful because identical values cancel each other:

x ^ x = 0

and:

x ^ 0 = x

XOR all numbers from 0 to n and also XOR every value present in nums. Every number that appears in both groups cancels out, leaving only the missing value.

Unlike the summation method, this approach does not build a potentially large arithmetic total, so it avoids intermediate sum overflow concerns.

Algorithm

Initialize xorExpected = 0 and xorActual = 0 to separately track the XOR of the expected range and the array values.
Traverse the array indices from 0 to n - 1.
XOR each index i into xorExpected, because these indices represent values from the expected range.
XOR nums[i] into xorActual to accumulate all values actually present in the array.
XOR n into xorExpected after the loop, because the expected range contains one additional value n.
Return xorExpected ^ xorActual. Every common value cancels, leaving only the missing number.

Dry Run

Missing Number Optimal Approach Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
6    int missingNumber(vector<int>& nums) {
7        int n = nums.size();
8
9        /*
10         * xorExpected tracks values from the complete range,
11         * while xorActual tracks values present in the array.
12         */
13        int xorExpected = 0;
14        int xorActual = 0;
15
16        for (int i = 0; i < n; i++) {
17            xorExpected ^= i;
18            xorActual ^= nums[i];
19        }
20
21        /*
22         * Indices cover only 0 to n - 1, so include n
23         * separately to complete the expected range.
24         */
25        xorExpected ^= n;
26
27        /*
28         * Values present in both groups cancel because x ^ x = 0,
29         * leaving only the number missing from nums.
30         */
31        return xorExpected ^ xorActual;
32    }
33};
34
35int main() {
36    vector<int> nums = {3, 0, 1};
37
38    Solution solution;
39    cout << solution.missingNumber(nums) << endl;
40
41    return 0;
42}

Complexity Analysis

Time Complexity: O(N), because the array is traversed once and each XOR operation takes constant time.

Space Complexity: O(1), because only a few integer variables are used.

Interview follow-up Questions

If nums[i] = i for every index from 0 to n - 1, then every value in that range is present. The only remaining value from the complete range 0 to n is n.

Missing Number

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Better Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Check Even or Odd

BIT Basics and Operators

XOR Basics

Missing Number

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Better Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Why does the sorting approach return n when every index matches?

Why is XOR useful for finding the missing number?

Which is preferable: the mathematical sum or XOR approach?

Does the array need to be sorted for the Sum or XOR approach?

Would these approaches work if more than one number were missing?

Why is the distinct-elements condition important?

Read Similar Blogs

Check Even or Odd

BIT Basics and Operators

XOR Basics