The jersey numbers
- O(n log n) · Hard
- Full plan
- Python
- JavaScript
- lists
- sorting
- loops
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):
passJavaScript
function bumps(requests) {
}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.