Skip to main content
Talentd

Missing Number - Solution & Explanation

EasyArrayHash TableMathBinary Search18 min readAsked at: Amazon, Microsoft, Apple +16
Practice this problem

Problem Statement

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 <= 104
  • 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.

The above C program calculates the sum of the array elements and subtracts it from the sum of numbers in the range [0, n], which is calculated using the formula n * (n + 1) / 2. This gives the missing number.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as no additional space is used beyond variables.

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.

This C solution utilizes XOR properties: iterates through the array, XORing indices and elements to find the single non-repeated element, which is the missing number.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), iterating through the array.
Space Complexity: O(1), using constant space.

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).

Code

PythonJavaC++GoTypeScriptRustJavaScriptPHP

Python

Java

C++

Go

TypeScript

Rust

JavaScript

PHP

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).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sum Formula Approach

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as no additional space is used beyond variables.

Bit Manipulation using XOR

Time Complexity: O(n), iterating through the array.
Space Complexity: O(1), using constant space.

Bitwise Operation—
Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sum FormulaO(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.

Video Solution

Missing Number - Blind 75 - Leetcode 268 - Python • NeetCode • 177,556 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Missing Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Couples Holding Hands

Next

Find the Duplicate Number