0192EasyArrayHash TableMathBinary SearchBit ManipulationSorting

Unclaimed Badge Number

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A site office owns one visitor badge for each whole number from 0 up to and including n. At closing time a clerk empties the drop tray and writes down what she finds there.

You get her note as the array returned. Its length is n, no number shows up twice, and each number she wrote sits somewhere in 0 through n inclusive, so exactly one badge of the set failed to come back.

Report the number printed on the badge that is still out.

Examples

Example 1

Input: returned = [2, 5, 0, 1, 4]
Output: 3

Five badges came back, so the office owns badges 0 through 5. Only 3 is absent from the tray.

Example 2

Input: returned = [0]
Output: 1

One badge came back out of the pair numbered 0 and 1, and the one still out is the higher of the two.

Example 3

Input: returned = [5, 3, 1, 0, 2, 6]
Output: 4

The tray covers 0 through 6 apart from 4, which never made it back.

Constraints

n == returned.length
1 <= n <= 10^4
0 <= returned[i] <= n
No value repeats inside returned
Exactly one value of 0..n is absent from returned

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def unclaimed_badge(returned: list[int]) -> int:

Java

public int unclaimedBadge(int[] returned)

The intended approach

Time O(n)Space O(1)

The whole set 0..n has a total you can write down in closed form. Whatever the tray adds up to falls short of that total by exactly the number on the missing badge, so subtract one sum from the other.

Pythonentry point: unclaimed_badge

def unclaimed_badge(returned):
    # Time O(n): one addition per badge in the tray.
    # Space O(1): two running integers, no lookup table.
    n = len(returned)
    full = n * (n + 1) // 2
    for value in returned:
        full -= value
    return full

The obvious version

Drop the tray into a membership set, then test 0, 1, 2, ... until one of them is not there.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_unclaimed_badge(returned):
    present = set(returned)
    for value in range(len(returned) + 1):
        if value not in present:
            return value
    return -1

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in