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.

Description Solution Video 12:11

268. Missing Number

Easy72.4% acceptance19 companies

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: