DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Missing Number

easyArrays and hashing Must-doAWS Cloud Support

Problem statement

A list nums holds n different integers, all taken from the range 0 to n inclusive. That range has n + 1 values, so exactly one of them is not in the list. Return the missing value.

A practical version: a job was meant to write shards 0 to n, one file each, and you have the list of shard numbers that actually landed. Which one is missing?

Examples

Example 1

Input: nums = [3, 0, 1, 4]

Output: 2

Explanation: n is 4, so the range is 0 to 4. Only 2 is absent.

Example 2

Input: nums = [1, 2]

Output: 0

Explanation: n is 2, so the range is 0 to 2, and 0 is absent.

Hints

Approach

The full range 0..n always sums to n * (n + 1) / 2. The list holds every value except one, so the gap between the expected sum and the actual sum is exactly the missing value.

  1. Let n = len(nums).
  2. Compute expected = n * (n + 1) / 2.
  3. Return expected - sum(nums).

In Java the code uses long so the multiplication cannot overflow for large n.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def missingNumber(self, nums: list[int]) -> int:
n = len(nums)
return n * (n + 1) // 2 - sum(nums)

Follow-up questions

  • Two numbers are missing instead of one. How do you find both?
  • The range starts at an arbitrary value a instead of 0. What changes?

Frequently asked questions

Yes, with XOR. XOR every index 0..n together with every value in the list. Each present value cancels itself out, and only the missing one remains. It is also O(n) time and O(1) space, and it cannot overflow.

If the missing value is n itself, the maximum in the list is n - 1. Using the maximum would make you look at the wrong range and return a wrong answer.

Finding the gap in a numbered sequence is a routine task: a missing shard, a skipped sequence number in replicated logs, or a batch ID that never reported. The sum trick is a neat way to find one gap without storing anything.