Skip to the content

The jersey numbers

Problem

On team photo day, every player shows up with the number they want on their back, but no two jerseys on a team can be the same. They go one at a time, in the order of the list: if their number is free, they keep it; if not, they move up to the next free number, with no upper limit. The kit manager has already noticed that the order does not change the total.

Write a function that takes requests, a list of integers from 0 up (it may be empty), and returns the sum of how far each number moved up. With [3, 2, 1, 2, 1, 7]: the 3, the 2 and the first 1 stay; the second 2 clashes, and 3 is taken too, so it reaches 4 (up 2); the second 1 moves up to 5 (up 4); the 7 stays. Return 6. If nobody clashes, or there is nobody, return 0.

Examples

  • The example

    [3, 2, 1, 2, 1, 7] → 6

  • Nobody clashes

    [4, 8, 1] → 0

  • Four ask for the same one

    [5, 5, 5, 5] → 6

  • A single player

    [7] → 0

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

Python

def bumps(requests):
    pass

JavaScript

function bumps(requests) {
}
Solve this challenge

It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.

More O(n log n) challenges

See all challenges →