DSA SheetEasy
EditorialPractice

SORTING › CYCLIC SORT

Missing Number

EasyEditorial · 5 minGenerated by gpt-5.6-luna · Aug 12

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionthe missing value is the only thing that cannot cancel

The array contains every number from 0 through n except one. If you combine all numbers in that complete range with all numbers in nums using XOR, every value that appears in the array appears twice: once in the range and once in nums. The missing value appears only in the range.

XOR has exactly the cancellation rules needed here: x ^ x is 0, and x ^ 0 is x. Because XOR is commutative and associative, you do not need to keep the range and the array in separate structures or put values into their correct positions. One accumulator can combine both sources in any order, leaving the missing number behind.

Approachcombine both collections without sorting or extra storage

  1. Set n to nums.size() and start the accumulator with n, because the loop will visit only range values 0 through n - 1 and the complete range also includes n.
  2. For each index i from 0 through n - 1, XOR the accumulator with i and nums[i]. This includes every range value and every array value exactly once in the combined expression, so matching values cancel.
  3. Return the accumulator after the loop. Every present number has contributed twice, while the missing number contributed once, so no search or final scan is necessary.

Complexityconstant working memory and one pass

MEASUREBOUNDWHY
TimeO(n)The loop performs one constant-time XOR operation for each of the n array positions, and each position is processed exactly once. No sorting, lookup structure, or repeated scan is performed.
SpaceO(1) extraOnly n and the XOR accumulator are stored. The input array and the returned integer are not working memory, and this constant bound does not degrade for any input arrangement.
Here n is the length of nums.

Annotated solutionC++ · one-pass XOR cancellation

CPPXOR the range and array values together, leaving the missing value.
#include <vector>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int xor_all = n;

        for (int i = 0; i < n; i++) {
            xor_all ^= i ^ nums[i];
        }

        return xor_all;
    }
};

Starting xor_all with n is the compact part of the implementation. The loop contributes indices 0 through n - 1, while the initial value contributes n, so the accumulator has seen the entire required range. Each nums[i] is added to that same expression. At the end, duplicate values cancel regardless of their positions in the array.

The arithmetic alternativesame asymptotic bounds, different cancellation method

CPPSubtract every array value from the arithmetic sum of 0 through n.
#include <vector>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        long long n = nums.size();
        long long expected = n * (n + 1) / 2;

        for (int value : nums) {
            expected -= value;
        }

        return static_cast<int>(expected);
    }
};

The sum version is a reasonable alternative rather than a strictly better solution. It starts with the expected sum of 0 through n and subtracts every value that is present, so the remainder is missing. It has O(n) time and O(1) extra space just like XOR. Using long long for the intermediate sum also keeps the arithmetic safe if the input bound is increased later.

Common mistakestwo wrong expressions that look almost right