Missing Number

easy
Bit ManipulationArrayMathBit Manipulation

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array. Each number appears at most once.

Examples

Example 1

  • Input: nums = [3,0,1]
  • Output: 2
  • Explanation: n = 3 since there are 3 numbers. The number 2 is missing from the range [0, 3].

Example 2

  • Input: nums = [0,1]
  • Output: 2
  • Explanation: n = 2 since there are 2 numbers. The number 2 is missing from the range [0, 2].

Example 3

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

Constraints

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All the numbers in nums are unique.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Sum Formula

Intuition

The sum of all integers from 0 to n is n * (n + 1) / 2. If one number is missing from the array, the difference between this expected sum and the actual sum of the array elements gives us the missing number. This is a clean mathematical approach that avoids any extra data structures.

Algorithm

  1. Compute `n` as the length of the array.
  2. Calculate the expected sum: `n * (n + 1) / 2`.
  3. Calculate the actual sum of all elements in the array.
  4. Return `expectedSum - actualSum`.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }
};
Java 21
class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }
}
Python 3.12
from typing import List


class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum
Go 1.26
func missingNumber(nums []int) int {
    n := len(nums)
    expectedSum := n * (n + 1) / 2
    actualSum := 0
    for _, num := range nums {
        actualSum += num
    }
    return expectedSum - actualSum
}
Approach 2

XOR Bit Manipulation

Intuition

XOR has the property that a ^ a = 0 and a ^ 0 = a. If we XOR all numbers from 0 to n together with all numbers in the array, every number that appears in both will cancel out, leaving only the missing number. This avoids potential integer overflow issues that the sum approach can have with very large n.

Algorithm

  1. Initialize `xor` to `0`.
  2. XOR every index from `0` to `n - 1` and every element in the array into `xor`.
  3. XOR `n` into the result as well (since indices only go to `n - 1`).
  4. Return `xor`, which now equals the missing number.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int xorResult = n;
        for (int i = 0; i < n; i++) {
            xorResult ^= i ^ nums[i];
        }
        return xorResult;
    }
};
Java 21
class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int xorResult = n;
        for (int i = 0; i < n; i++) {
            xorResult ^= i ^ nums[i];
        }
        return xorResult;
    }
}
Python 3.12
from typing import List


class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        xor_result = n
        for i in range(n):
            xor_result ^= i ^ nums[i]
        return xor_result
Go 1.26
func missingNumber(nums []int) int {
    n := len(nums)
    xorResult := n
    for i := 0; i < n; i++ {
        xorResult ^= i ^ nums[i]
    }
    return xorResult
}

Frequently asked questions

What is the optimal time complexity of Missing Number?

The most efficient approach in this guide ("XOR Bit Manipulation") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Missing Number use?

Missing Number is a easy-level Bit Manipulation problem involving Array, Math, Bit Manipulation. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Missing Number be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
nums=
[3,0,1]
Expected Output
2