The Missing Badge

EasyArrays & Hashing

Problem

A conference printed badges numbered 0 to n, one of each. At the end of the day n badges were returned, all distinct, and stored in nums. Exactly one badge number is missing.

Return the missing number using O(1) extra space.

Example 1

Input:
nums = [3, 0, 1]
Output:
2

n = 3, so the badges are 0..3; 2 never came back.

Example 2

Input:
nums = [0, 1]
Output:
2

The missing one can be n itself.

Constraints

  • 1 ≤ n = nums.length ≤ 10^4
  • 0 ≤ nums[i] ≤ n
  • All values are distinct.

Hint

Show the first hint

You know exactly which numbers should be present. What can you compute from 'all of them' and 'the ones you have'?

Walkthrough

How to approach it

01Clarify before coding

  • Can the missing number be 0 or n? Yes, any value in 0..n.
  • Are values distinct? Yes, so no duplicate tricks are needed.
  • Is a hash set allowed? It works, but the target is O(1) extra space.

02Brute force

Sort the array and return the first index i where nums[i] != i (or n if none); or put everything in a set and probe 0..n.

Cost: Sorting is O(n log n) time; the set is O(n) time but O(n) space.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.