Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Missing Number

Missing Number

Master this topic with zero to advance depth.

Missing Number

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.

Easy

Examples

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

n = 3. Range is [0,3]. 2 is missing.

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

n = 2. Range is [0,2]. 2 is missing.

Approach 1

Level I: Brute Force (Sorting)

Intuition

Sort the array and check if each index matches the value at that index. The first index ii where nums[i] != i is the missing number. If all match, the missing number is nn.

Thought Process

  1. Sort nums in ascending order.
  2. Iterate ii from 00 to n−1n - 1:
    • If nums[i] != i, return i.
  3. If loop finishes, return n.

Pattern: Sorting

⏱ O(N log N) - Due to sorting.💾 O(1) or O(N) depending on the sort implementation.
java
import java.util.Arrays;

public class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) return i;
        }
        return nums.length;
    }
}
Approach 2

Level II: Math (Sum Formula)

Intuition

The sum of the first nn numbers is n(n+1)2\frac{n(n+1)}{2}. By subtracting the sum of all elements in the array from this total sum, we obtain the missing number.

⏱ $O(N)$💾 $O(1)$
java
class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int x : nums) actualSum += x;
        return expectedSum - actualSum;
    }
}
Approach 3

Level III: Optimal (XOR)

Intuition

XORing a number with itself results in 0 (x⊕x=0x \oplus x = 0). If we XOR all numbers in the range [0,n][0, n] and all numbers in the array, every number present in the array will appear twice and cancel out, leaving only the missing number.

Thought Process

  1. Initialize missing = n (or 0).
  2. Iterate through the array:
    • missing ^= i ^ nums[i]
  3. Return missing.

Pattern: XOR Cancellation

⏱ O(N) - Single pass through the array.💾 O(1) - Constant storage.

Detailed Dry Run

nums = [3, 0, 1], n = 3 missing = 3 i=0: missing = 3 ^ 0 ^ 3 = 0 i=1: missing = 0 ^ 1 ^ 0 = 1 i=2: missing = 1 ^ 2 ^ 1 = 2 Result: 2

java
public class Solution {
    public int missingNumber(int[] nums) {
        int xor = nums.length;
        for (int i = 0; i < nums.length; i++) {
            xor ^= i ^ nums[i];
        }
        return xor;
    }
}
← Previous QuestionSum of Two Integers
Next Question →Count Triplets That Can Form Two Arrays of Equal XOR