Минимизируйте X так, чтобы массив можно было сделать 0, уменьшив элементы меньше, чем X

Дан массив A[] размера N . На каждом шаге уменьшайте элемент до 0 и уменьшайте все ненулевые элементы на 1, пока все элементы не станут 0. Найдите минимально возможное значение X , такое, чтобы массив можно было сделать 0, удалив значения, меньшие или равные X в каждый шаг.

Примеры:

Input: N = 4, A = {7, 18, 16, 14}
Output: 15
Explanation: At the beginning of the operation, the array has {7, 18, 16, 14}
Make 1st element 0, remaining array elements {0, 17, 15, 13}
Make 3rd element 0,  remaining array elements {0, 16, 0, 12}
Make 4th element 0, remaining array elements {0, 15, 0, 0}
Make 2nd element 0, remaining array elements {0, 0, 0, 0}
Therefore the minimum value of X needs to be 15 units.

Input: N = 1, A = {3}
Output: 3
Explanation: X has to be 3

Подход: Эту проблему можно решить с помощью жадного алгоритма .

Make the smallest element 0 first so that all  the greater elements are reduced by 1 so that X can be minimized.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Отсортируйте заданный массив.
• Начните создавать элементы 0, начиная с самого маленького элемента.
• Следовательно, для каждого i-го элемента массива значение в этот момент уменьшилось бы на i единиц, т.е. value = A[i] – i .
• Найдите максимальное значение среди A[i] – i , чтобы все элементы стали равными 0.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N * log N)
Вспомогательное пространство: O(1)