Минимизируйте сумму чисел, необходимую для преобразования массива в перестановку первых N натуральных чисел.

Учитывая массив A[] размера N , задача состоит в том, чтобы найти минимальную сумму чисел, которую необходимо добавить к элементам массива, чтобы преобразовать массив в перестановку от 1 до N . Если массив нельзя преобразовать в желаемую перестановку, выведите -1 .

Примеры:

Input: A[] = {1, 1, 1, 1, 1}
Output: 10
Explanation: Increment A[1] by 1, A[2] by 2, A[3] by 3, A[4] by 4, thus A[] becomes {1, 2, 3, 4, 5}.
Minimum additions required = 1 + 2 + 3 + 4 = 10

Input: A[] = {2, 2, 3}
Output: -1

Подход: Идея состоит в том, чтобы использовать сортировку. Выполните следующие действия, чтобы решить эту проблему:

• Инициализировать переменную и сохранить требуемый результат.
• Отсортируйте данный массив A[] в порядке возрастания.
• Пройдите массив A[] с помощью переменной i
  • Если значение A[i] > i+1 , обновите значение an до -1 и прервите цикл.
  • В противном случае увеличьте an на разницу i+1 и A[i] .
• Выведите значение ans в качестве результата.

Ниже приведена реализация вышеуказанного подхода:

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