Make Array Distinct (Selling Shoes 🩰)
MediumAsked in:Amazon•Stage:Online Assessment
arraysortinggreedy
Problem Statement
Given an array of integers representing shoe sizes, you may increase any element by 1 any number of times. Determine the minimum total number of increments required so that all elements become pairwise distinct. The order of elements does not matter, only their final values matter.
Input Format
The first line contains an integer n, the number of shoes. The second line contains n space‑separated integers a1,a2,…,an representing the initial sizes.
Output Format
Print a single integer – the minimal total number of increments needed to make all array elements distinct.
Constraints
- 1 <= n <= 10^5
- 0 <= a[i] <= 10^9
- The answer fits in a 64‑bit signed integer