Make All Elements Distinct (Amazon London)
EasyAsked in:Amazon•Stage:Online Assessment
arrayhash_table
Problem Statement
Given an array of n integers, you may increment any element by 1 any number of times. Determine the minimum total number of increments required so that all array elements become distinct. Return this minimum count.
Input Format
The first line contains an integer n, the size of the array. The second line contains n space‑separated integers a1,…,an.
Output Format
Print a single integer – the minimal number of increment operations needed to make all elements distinct.
Constraints
- 1 <= n <= 10^5
- -10^9 <= a[i] <= 10^9
- Time complexity should be O(n log n) or better