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

Опубликовано: 22 Сентября, 2022

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

Примеры :

Input: arr[] = {5, 4, 1, 10}
Output: 5
Explanation: 
One of the possible way to perform operation is:
Operation 1: Select the indices 1 and 3 and then increment arr[1] by 1 and decrement arr[3] by 1. Thereafter, the array modifies to {5, 5, 1, 9}.
Operation 2: Select the indices 2 and 3 and then increment arr[2] by 1 and decrement arr[3] by 1. Thereafter, the array modifies to {5, 5, 2, 8}.
Operation 3: Select the indices 2 and 3 and then increment arr[2] by 1 and decrement arr[3] by 1. Thereafter, the array modifies to {5, 5, 3, 7}.
Operation 4: Select the indices 2 and 3 and then increment arr[2] by 1 and decrement arr[3] by 1. Thereafter, the array modifies to {5, 5, 4, 6}.
Operation 5: Select the indices 2 and 3 and then increment arr[2] by 1 and decrement arr[3] by 1. Thereafter, the array modifies to {5, 5, 5, 5}.
Therefore, the total number of move needed is 5. Also, it is the minimum possible moves needed.

Input: arr[] = {1, 4}
Output: -1

Подход: Данная проблема может быть решена на основе следующих наблюдений:

  • It can be observed that in one move thesum of the arrayremains the same therefore, if the sum of the array is not divisible N then it is impossible to make all the array elements equal.
  • Otherwise, each array element will be equal to the sum of the array divided by N.
  • Therefore, the idea is to use the two pointer technique to find the minimum count of moves needed to make all the array elements equal to the sum/N.

Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную, скажем , как 0 , чтобы сохранить количество необходимых ходов.
  • Найдите сумму массива и сохраните ее в переменной, скажем, sum .
  • Теперь, если сумма не делится на N , выведите « -1 ». В противном случае обновите сумму как sum =sum/N.
  • Отсортируйте массив в порядке возрастания.
  • Инициализируйте переменные, скажем, i как 0 и j как N – 1 для перебора массива.
  • Повторяйте, пока i не станет меньше j, и выполните следующие шаги:
    • Если увеличение arr[i] до суммы меньше, чем уменьшение arr[j] до суммы , добавьте sum – arr[i] к ans , а затем обновите arr[i] и arr[j] и затем увеличьте i на 1 .
    • В противном случае добавьте arr[j] – sum к ans и обновите arr[i] и arr[j] , а затем уменьшите j на 1.
  • Наконец, после выполнения вышеуказанных шагов выведите значение, хранящееся в файле ans .

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ