0221EasyArrayHash TableBit ManipulationSorting

Bib Number Mixup

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 road race orders one bib per runner, so a field of n runners should receive the numbers 1 through n, each on a single bib. The press misfired: one number came out on two bibs and one number never came out at all. Every other number landed on exactly one bib.

You are given the integer array bibs of length n holding the number printed on each bib, in the order the bibs came off the press. Return a two-element array [repeated, absent], where repeated is the number printed on two bibs and absent is the number in the range 1 to n printed on none of them.

Examples

Example 1

Input: bibs = [3, 1, 3]
Output: [3, 2]

Three bibs came off the press for a field of 3 runners. The number 3 sits on two of them and no bib carries 2, so the answer is [3, 2].

Example 2

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

Two bibs carry the number 2 and no bib carries 4.

Example 3

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

The number 5 appears on two bibs, and 4 is the number in the range 1 to 6 that is missing.

Constraints

2 <= bibs.length <= 10^4
1 <= bibs[i] <= 10^4
Exactly one number in the range 1 to bibs.length appears twice in bibs
Exactly one number in the range 1 to bibs.length does not appear in bibs
Every other number in the range 1 to bibs.length appears exactly once

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 find_bib_slip(bibs: list[int]) -> list[int]:

Java

public int[] findBibSlip(int[] bibs)

The intended approach

Time O(n)Space O(n) for the tally

Every printed number lies in the range 1 to n, so keep a tally indexed by number and bump the slot for each bib. A second walk over the tally reports the number with two hits and the number with none.

Pythonentry point: find_bib_slip

def find_bib_slip(bibs):
    n = len(bibs)
    tally = [0] * (n + 1)
    for number in bibs:
        tally[number] += 1
    repeated = 0
    absent = 0
    for number in range(1, n + 1):
        if tally[number] == 2:
            repeated = number
        elif tally[number] == 0:
            absent = number
    return [repeated, absent]

The obvious version

For each candidate number from 1 to n, rescan the whole array and count how often it was printed, keeping the one counted twice and the one counted zero times. O(n^2).

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_find_bib_slip(bibs):
    n = len(bibs)
    repeated = 0
    absent = 0
    for number in range(1, n + 1):
        hits = 0
        for printed in bibs:
            if printed == number:
                hits += 1
        if hits == 2:
            repeated = number
        if hits == 0:
            absent = number
    return [repeated, absent]

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