268. Missing Number

Missing Number (LeetCode 268) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise XOR - Finding Single/Missing Number subpattern.

• Blind 75 · #74 of 75 · Bit Manipulation
• NeetCode 150 · #148 of 150 · Bit Manipulation
• NeetCode 250 · #246 of 250 · Bit Manipulation

How to solve Missing Number

Missing Number is a XOR for Single and Missing Numbers problem, part of Bit Manipulation Patterns. Use XOR properties to find single number, missing number, and duplicates.

Work towards the solution in these steps:

1. Think about how you might identify a missing number when given a sequence of unique numbers within a known range.
2. Consider how bitwise operations, especially XOR, can help find differences between two sets of numbers.
3. Remember that XORing a number with itself results in zero, and XORing with zero results in the number itself.

The reference solution runs in O(n) time and O(1) space.

The Missing Number solution and editorial walks through the full approach with reference code.

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?

Topics and companies

Topics: Array, Hash Table, Math, Binary Search, Bit Manipulation, Sorting.

Reported in interviews at Capital One, Amazon, Facebook, Apple, Microsoft, Oracle, Goldman Sachs, Cisco, Arista Networks.

How to practise Missing Number on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Missing Number in the code editor, or read the Missing Number editorial for a worked solution with its approach and complexity analysis.

Where Missing Number sits in the DSA pattern sheet

• Bit Manipulation Patterns pattern guide
• Bitwise XOR - Finding Single/Missing Number subpattern
• The full DSA patterns sheet

Problems related to Missing Number

Other problems that use the same Bitwise XOR - Finding Single/Missing Number and Bit Manipulation Patterns techniques:

• Find the Difference — Easy, same subpattern
• Single Number — Easy, same subpattern
• Single Number II — Medium, same subpattern
• Sum of Two Integers — Medium, same subpattern
• Bitwise AND of Numbers Range — Medium, same pattern
• Counting Bits — Easy, same pattern

Missing Number FAQ