Make Badge Numbers Unique

MediumGreedy

Problem

A conference printed badge numbers badges, but some numbers repeat. A badge number can only be increased, one unit at a time, and each increase costs one reprint.

Return the minimum number of increments needed so that all badge numbers are distinct.

Example 1

Input:
badges = [3, 1, 1]
Output:
1

Raise one of the 1s to 2: [3, 1, 2].

Example 2

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

Sorted 1, 2, 2, 3, 4, 4 becomes 1, 2, 3, 4, 5, 6: increments 0 + 0 + 1 + 1 + 1 + 2.

Constraints

  • 1 ≤ badges.length ≤ 10^5
  • 0 ≤ badges[i] ≤ 10^5

Hint

Show the first hint

Sort first. In sorted order, what is the smallest value the i-th badge can end up with?

Walkthrough

How to approach it

01Clarify before coding

  • Can numbers decrease? No, increments only.
  • Is there an upper bound on final numbers? No.
  • Could the answer overflow 32 bits? It can exceed 10^9 for large inputs, so use 64-bit (Python and JS numbers are fine).

02Brute force

Repeatedly find a duplicate and increment it until no duplicates remain.

Cost: Up to O(n²) increments, each with a duplicate search: far too slow for 10^5 equal values.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.