90. Missing Number · DSA Practice

nums contains n distinct numbers from the range [0, n]. Return the one number missing from the range.

Example 1

Input: nums = [3,0,1]

Output: 2

Example 2

Input: nums = [0,1]

Output: 2

Hint 1

Sum formula: n(n+1)/2 − sum(nums).

Hint 2

Or XOR all indices and values: everything cancels except the missing number.

Bit ManipulationMath

Approach 1: Sort

Find the first index i with nums[i] ≠ i.

⏱ Time O(n log n)💾 Space O(1)

Approach 2: Gauss sum

Expected sum minus actual sum.

⏱ Time O(n)💾 Space O(1)

Approach 3: XOR ✅

Indices and values cancel in pairs.

⏱ Time O(n)💾 Space O(1)

Reference solution for XOR (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        x = len(nums)
        for i, v in enumerate(nums):
            x ^= i ^ v        # every index and value pairs up except the missing one
        return x

class Solution {
    public int missingNumber(int[] nums) {
        int x = nums.length;
        for (int i = 0; i < nums.length; i++) x ^= i ^ nums[i];
        return x;
    }
}

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int x = nums.size();
        for (int i = 0; i < (int)nums.size(); i++) x ^= i ^ nums[i];
        return x;
    }
};

function missingNumber(nums) {
  let x = nums.length;
  for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i];
  return x;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

This problem is explained in the lesson Bit Manipulation.