Missing Number

Easy Problem 148 of 151 Java and Python

Problem

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

Example 1

Input: nums = [3, 0, 1]
Output: 2

Example 2

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

Constraints

1 ≤ n ≤ 10⁴
All numbers are unique.
Follow-up: O(1) extra space.

Explanation

The numbers 0…n add up to n(n + 1) / 2. Subtract the actual sum and what remains is the missing number.

The XOR version avoids any overflow risk: XOR every index 0…n with every value; everything present cancels out, leaving the missing number.

Approach 1 · Naive

Hash set lookup

Time O(n)
Space O(n)

Put every number in a set, then check 0…n for the one that is absent.

Add all numbers to a set.
Return the first i in 0…n not in the set.

Java

import java.util.*;

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            seen.add(num);
        }
        for (int i = 0; i <= nums.length; i++) {
            if (!seen.contains(i)) {
                return i;
            }
        }
        return -1;
    }
}

Python

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        seen = set(nums)
        for i in range(len(nums) + 1):
            if i not in seen:
                return i
        return -1

Approach 2 · Optimal

XOR indexes and values

Time O(n)
Space O(1)

Start with n and XOR in every index and every value; pairs cancel, the missing number remains.

result = n.
For each i, result ^= i ^ nums[i].
Return result.

Java

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

Python

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        result = len(nums)
        for i, num in enumerate(nums):
            result ^= i ^ num
        return result

Complexity compared

Approach	Time	Space
Naive Hash set lookup	O(n)	O(n)
Optimal XOR indexes and values	O(n)	O(1)

Key takeaways

The sum formula n(n + 1) / 2 - sum(nums) is also O(1) space; mention overflow for large n in Java.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem