268. Missing Number - Solution & Explanation

Q: Is Missing Number easy or hard?

Missing Number is classified as an Easy problem on LeetCode with a high acceptance rate. The logic is simple once you recognize the math formula or XOR pattern, which is why it often appears in early interview rounds.

Q: Missing Number Python/Java solution

In Python or Java, the common implementation uses either the sum formula or XOR technique. Both iterate once through the array and use constant memory, giving O(n) time and O(1) space complexity.

Q: How to solve Missing Number in O(n)?

Iterate through the array once while maintaining either a running sum or a running XOR. For the sum method, compute n*(n+1)/2 and subtract the array sum. For the XOR method, XOR all indices and elements so duplicates cancel out and the remaining value is the missing number.

Q: What is the best approach for Missing Number?

The optimal solutions run in O(n) time and O(1) space. Two common approaches are the Sum Formula method and the XOR method. The sum formula calculates the expected sum of numbers from 0..n and subtracts the actual array sum. The XOR approach cancels out matching numbers using XOR properties, leaving the missing value.

Q: Is Missing Number asked at Google/Amazon/Meta?

Missing Number is a classic array and bit manipulation interview problem that has appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of basic algorithmic patterns such as arithmetic formulas and XOR tricks.

Q: What data structure is used in Missing Number?

The problem primarily uses an array as input. Efficient solutions rely on mathematical reasoning or bit manipulation rather than additional data structures like hash tables.

Q: What is the time complexity of Missing Number?

Both optimal approaches run in O(n) time because the algorithm scans the array once. The space complexity is O(1) since only a few variables are used and no additional data structures are required.

The problem

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.

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

n == nums.length
1 <= n <= 10⁴
0 <= nums[i] <= n
All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Approach overview

Problem Overview: You get an array containing n distinct numbers taken from the range 0..n. Exactly one number from that range is missing. The task is to identify the missing value efficiently without modifying the array.

Approach 1: Sum Formula Approach (O(n) time, O(1) space)

This approach relies on a simple mathematical observation. The sum of numbers from 0 to n is n * (n + 1) / 2. If you iterate through the array and compute the actual sum of its elements, the difference between the expected sum and the actual sum gives the missing number. The algorithm performs one pass through the array and a constant amount of arithmetic work.

The key insight is that the array contains every value in the range except one. Subtracting the observed total from the theoretical total reveals exactly which value is absent. This approach uses constant extra memory and avoids sorting or additional data structures, which makes it ideal for large inputs. The technique is rooted in simple math properties applied to an array.

Approach 2: Bit Manipulation using XOR (O(n) time, O(1) space)

The XOR method leverages a useful property of the XOR operation: a ^ a = 0 and a ^ 0 = a. If you XOR all numbers from 0..n and also XOR every element in the array, every number that appears in both sets cancels out. The only value left after all XOR operations is the missing number.

Implementation is straightforward. Iterate through the array while maintaining a running XOR of indices and values. For example, XOR the index and the element during the same loop. At the end, XOR with n to complete the full range. Because XOR operations are constant time and you only traverse the array once, the algorithm runs in linear time with constant extra space.

This technique is common in problems involving unique or missing elements and highlights the power of bit manipulation. It avoids potential integer overflow issues that may appear with the arithmetic sum formula in languages with strict integer limits.

Recommended for interviews: Both approaches are considered optimal and run in O(n) time with O(1) space. Interviewers often expect either the sum formula or the XOR solution. The sum formula demonstrates mathematical reasoning and clean code, while the XOR approach shows deeper understanding of bit operations. Explaining both during an interview signals strong problem-solving range.

Approach 1: Sum Formula Approach

This approach uses the formula for the sum of the first n natural numbers: Sum = n * (n + 1) / 2. By calculating the sum of the numbers from the array and subtracting it from the expected sum, we can find the missing number.

Python

class Solution:
    def missingNumber(self, nums):
        n = len(nums)
        total = n * (n + 1) // 2
        return total - sum(nums)

# Usage
nums = [3, 0, 1]
sol = Solution()
print(f"Missing number: {sol.missingNumber(nums)}")

Java

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int total = n * (n + 1) / 2;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return total - sum;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 0, 1};
        System.out.println("Missing number: " + sol.missingNumber(nums));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    int total = n * (n + 1) / 2;
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    return total - sum;
}

int main() {
    vector<int> nums = {3, 0, 1};
    cout << "Missing number: " << missingNumber(nums) << endl;
    return 0;
}

JavaScript

function missingNumber(nums) {
    const n = nums.length;
    const total = n * (n + 1) / 2;
    const sum = nums.reduce((acc, val) => acc + val, 0);
    return total - sum;
}

// Usage
const nums = [3, 0, 1];
console.log("Missing number:", missingNumber(nums));

#include <stdio.h>

int missingNumber(int* nums, int numsSize) {
    int total = numsSize * (numsSize + 1) / 2;
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    return total - sum;
}

int main() {
    int nums[] = {3, 0, 1};
    int missing = missingNumber(nums, 3);
    printf("Missing number: %d\n", missing);
    return 0;
}

using System;

public class Solution {
    public int MissingNumber(int[] nums) {
        int n = nums.Length;
        int total = n * (n + 1) / 2;
        int sum = 0;
        foreach (int num in nums) {
            sum += num;
        }
        return total - sum;
    }

    public static void Main(string[] args) {
        int[] nums = {3, 0, 1};
        Solution sol = new Solution();
        Console.WriteLine("Missing number: " + sol.MissingNumber(nums));
    }
}

This Python solution calculates the expected total using n * (n + 1) // 2 and uses the built-in sum() function to find the sum of the array. The missing number is found by subtracting these sums.

Complexity

Time Complexity: O(n), because of the summation over the array.
Space Complexity: O(1), as only a few scalar variables are used.

Try this approach in the editor

Approach 2: Bit Manipulation using XOR

An efficient approach is using XOR. XORing a number with itself results in zero (n ^ n = 0), and XOR of any number with zero keeps the number unchanged (n ^ 0 = n). By XORing all indices and array elements together, each number present in both will cancel out, leaving the missing number.

Python

class Solution:
    def missingNumber(self, nums):
        xor_result = 0
        for i, num in enumerate(nums):
            xor_result ^= i ^ num
        return xor_result ^ len(nums)

# Usage
nums = [3, 0, 1]
sol = Solution()
print(f"Missing number: {sol.missingNumber(nums)}")

Java

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 0, 1};
        System.out.println("Missing number: " + sol.missingNumber(nums));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int missingNumber(vector<int>& nums) {
    int xor_result = 0;
    for (int i = 0; i < nums.size(); i++) {
        xor_result ^= i ^ nums[i];
    }
    xor_result ^= nums.size();
    return xor_result;
}

int main() {
    vector<int> nums = {3, 0, 1};
    cout << "Missing number: " << missingNumber(nums) << endl;
    return 0;
}

JavaScript

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

// Usage
const nums = [3, 0, 1];
console.log("Missing number:", missingNumber(nums));

#include <stdio.h>

int missingNumber(int* nums, int numsSize) {
    int xor_result = 0;
    for (int i = 0; i < numsSize; i++) {
        xor_result ^= i ^ nums[i];
    }
    xor_result ^= numsSize;
    return xor_result;
}

int main() {
    int nums[] = {3, 0, 1};
    int missing = missingNumber(nums, 3);
    printf("Missing number: %d\n", missing);
    return 0;
}

using System;

public class Solution {
    public int MissingNumber(int[] nums) {
        int xorResult = 0;
        for (int i = 0; i < nums.Length; i++) {
            xorResult ^= i ^ nums[i];
        }
        xorResult ^= nums.Length;
        return xorResult;
    }

    public static void Main(string[] args) {
        int[] nums = {3, 0, 1};
        Solution sol = new Solution();
        Console.WriteLine("Missing number: " + sol.MissingNumber(nums));
    }
}

Using XOR, the Python solution finds the missing number by cancelling pairs and retaining the non-paired value.

Complexity

Time Complexity: O(n), iterating over the elements and indices.
Space Complexity: O(1), no extra storage required beyond scalars.

Try this approach in the editor

Approach 3: Bitwise Operation

The XOR operation has the following properties:

Any number XOR 0 is still the original number, i.e., x \oplus 0 = x;
Any number XOR itself is 0, i.e., x \oplus x = 0;

Therefore, we can traverse the array, perform XOR operation between each element and the numbers [0,..n], and the final result will be the missing number.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

TypeScript

function missingNumber(nums: number[]): number {
    const n = nums.length;
    let ans = n;
    for (let i = 0; i < n; ++i) {
        ans ^= i ^ nums[i];
    }
    return ans;
}

func missingNumber(nums []int) (ans int) {
	n := len(nums)
	ans = n
	for i, v := range nums {
		ans ^= (i ^ v)
	}
	return
}

Rust

impl Solution {
    pub fn missing_number(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        let mut ans = n;
        for (i, v) in nums.iter().enumerate() {
            ans ^= (i as i32) ^ v;
        }
        ans
    }
}

PHP

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function missingNumber($nums) {
        $n = count($nums);
        $sumN = (($n + 1) * $n) / 2;
        for ($i = 0; $i < $n; $i++) {
            $sumN -= $nums[$i];
        }
        return $sumN;
    }
}

Try this approach in the editor

Approach 4: Mathematics

We can also solve this problem using mathematics. By calculating the sum of [0,..n], subtracting the sum of all numbers in the array, we can obtain the missing number.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

TypeScript

function missingNumber(nums: number[]): number {
    const n = nums.length;
    let ans = n;
    for (let i = 0; i < n; ++i) {
        ans += i - nums[i];
    }
    return ans;
}

func missingNumber(nums []int) (ans int) {
	n := len(nums)
	ans = n
	for i, v := range nums {
		ans += i - v
	}
	return
}

Rust

impl Solution {
    pub fn missing_number(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        let mut ans = n;
        for (i, &v) in nums.iter().enumerate() {
            ans += (i as i32) - v;
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sum Formula Approach	Time Complexity: O(n), because of the summation over the array. Space Complexity: O(1), as only a few scalar variables are used.
Bit Manipulation using XOR	Time Complexity: O(n), iterating over the elements and indices. Space Complexity: O(1), no extra storage required beyond scalars.
Bitwise Operation	–
Mathematics	–

Complexity analysis

Approach	Time	Space	When to Use
Sum Formula	O(n)	O(1)	General case when arithmetic overflow is not a concern and you want the simplest implementation.
Bit Manipulation (XOR)	O(n)	O(1)	Preferred when demonstrating bit manipulation skills or avoiding overflow in languages with limited integer ranges.

Frequently asked questions

Is Missing Number easy or hard?

Missing Number is classified as an Easy problem on LeetCode with a high acceptance rate. The logic is simple once you recognize the math formula or XOR pattern, which is why it often appears in early interview rounds.

Missing Number Python/Java solution

In Python or Java, the common implementation uses either the sum formula or XOR technique. Both iterate once through the array and use constant memory, giving O(n) time and O(1) space complexity.

How to solve Missing Number in O(n)?

Iterate through the array once while maintaining either a running sum or a running XOR. For the sum method, compute n*(n+1)/2 and subtract the array sum. For the XOR method, XOR all indices and elements so duplicates cancel out and the remaining value is the missing number.

What is the best approach for Missing Number?

The optimal solutions run in O(n) time and O(1) space. Two common approaches are the Sum Formula method and the XOR method. The sum formula calculates the expected sum of numbers from 0..n and subtracts the actual array sum. The XOR approach cancels out matching numbers using XOR properties, leaving the missing value.

Is Missing Number asked at Google/Amazon/Meta?

Missing Number is a classic array and bit manipulation interview problem that has appeared in interviews at companies like Google, Amazon, and Meta. It tests understanding of basic algorithmic patterns such as arithmetic formulas and XOR tricks.

What data structure is used in Missing Number?

The problem primarily uses an array as input. Efficient solutions rely on mathematical reasoning or bit manipulation rather than additional data structures like hash tables.

What is the time complexity of Missing Number?

Both optimal approaches run in O(n) time because the algorithm scans the array once. The space complexity is O(1) since only a few variables are used and no additional data structures are required.

Missing Number solution and explanation

The problem

Approach overview

Approach 1: Sum Formula Approach

Approach 2: Bit Manipulation using XOR

Approach 3: Bitwise Operation

Approach 4: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Missing Number solution and explanation

The problem

Approach overview

Approach 1: Sum Formula Approach

Approach 2: Bit Manipulation using XOR

Approach 3: Bitwise Operation

Approach 4: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems