Минимум операций для изменения данного массива с не более чем 1 дубликатом в перестановку от 1 до N

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

Примеры:

Input: arr[] = {1, 2, 5, 3, 2} 
Output: 2 
Explanation: The given array contains 2 twice and 4 is missing from the array. Therefore, a 2 can be changed into 4 using two increment operations which is the minimum possible. 

Input: arr[] = {1, 2, 5, 3, 4} 
Output: 0 
Explanation: The given array already represents the permutation of integers from 1 to 5. 
 

Наивный подход: Данную проблему можно решить, просто найдя повторяющийся элемент и отсутствующий элемент в заданном массиве. Это можно легко сделать, отсортировав данный массив и проверив наличие дубликатов и отсутствующих элементов.

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

Эффективный подход: данная проблема может быть решена с помощью простого наблюдения, что сумма всех элементов перестановки из N целых чисел всегда равна N*(N+1)/ 2 . Следовательно, количество необходимых операций можно просто рассчитать по формуле | сумма элементов массива – N*(N+1)/ 2)| .

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

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