Classic problem #945MediumArrayGreedySortingCounting
Minimum Increment to Make Array Unique
Real-world version: Nudging Dials ApartTracked in this browser only
Read Minimum Increment to Make Array Unique on LeetCode(opens in a new tab)
The statement here is our own: the same inputs, outputs and technique.
A row of dials shows whole-number readings, and several dials may show the same reading. One nudge picks a single dial and raises its reading by 1.
Return the fewest nudges that leave no two dials showing the same reading.
Examples
Example 1
- Input
- dials = [0, 0]
- Output
- 1
One of the two dials climbs to 1, which takes a single nudge.
Example 2
- Input
- dials = [2, 2, 2, 2, 2]
- Output
- 10
Leave one dial where it is and lift the other four to 3, 4, 5 and 6, costing 1 plus 2 plus 3 plus 4.
Example 3
- Input
- dials = [1, 2, 3, 4, 5]
- Output
- 0
No two dials already share a reading, so nothing has to move.
Constraints
- 1 <= dials.length <= 10^5
- 0 <= dials[i] <= 10^5
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
Python
def min_increment_for_unique(dials: list[int]) -> int:Java
public int minIncrementForUnique(int[] dials)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's