Минимальные приращения, сделанные в массиве, чтобы arr[i] мог сделать все остальные элементы равными

Учитывая массив arr[] размера N , задача состоит в том, чтобы найти минимальное приращение, требуемое для элементов в массиве, так что, если какой-либо элемент говорит, что arr[i] распределен среди других, сделать N – 1 элемент равным.

Примеры:

Input: arr[] = {0, 0, 3}, N = 3
Output: 3
Explanation: Increments can be done in the following way:

• Increment element at index 0 by 1, so arr[] becomes {1, 0, 3}
• Increment element at index 1 by 2. so arr[] becomes {1, 2, 3}

Now, if any element is chosen and distributed in others, makes all N – 1 elements equal.

Lets say,  

• choose 1, add it to 2, so N – 1 elements become {3, 3}
• choose 2, add it to 1, so N – 1 elements become {3, 3}
• choose 3, add 2 of 3 to 1 and add 1 of 3 to 2, so N – 1 elements become {3, 3}

So, total increments = (1 + 2) = 3

Input: arr[] = {4, 3, 1, 6}, N = 4
Output:  4

Подход: Идея решения этой проблемы основана на наблюдении, что если (N-1)*mx , где mx — максимальный элемент массива, больше, чем сумма массива, тогда ответ будет просто (N-1) *mx – сумма. В противном случае, если (N-1)*mx меньше или равно сумме, возьмите временную переменную, скажем, temp , назначьте ей сумму / N – 1 . Если сумма по модулю N -1 не равна 0 , увеличьте temp на 1 и возьмите счетчик, чтобы сказать count , где count - это разница temp и mx . Обновить ответ = (count + mx) * (N – 1) и увеличить сумму на count.If sum равно (N-1)*mx return count , иначе вернуть count увеличенный с разницей (N-1)*mx и сумма . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменные mx и sum как 0 , чтобы найти сумму и максимальный элемент массива.
• Перебрать диапазон [0, N), используя переменную i , и выполнить следующие задачи:
  • Обновите значение mx как максимальное значение mx или arr[i] и добавьте значение arr[i] к переменной sum.
• Инициализируйте переменную ans как (N-1)*mx.
• Если ответ больше суммы , то в качестве ответа верните сумму ответа.
• В противном случае инициализируйте переменную temp как sum/(N-1) + sum%(N-1).
• Инициализируйте переменную count как temp – mx .
• Установите значение ans как (count + mx)*(N-1).
• Добавьте значение count к переменной sum.
• Если sum равно ans, то вернуть значение count в качестве ответа, иначе вернуть count + ans – sum.

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

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