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

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

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

Примеры:

Input: arr[] = {5, 4, 1, 10}
Output: 5
Explanation:  
One of the possible ways to perform operations 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 moves needed is 5. Also, it is the minimum possible moves needed.

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

Наивный подход: обратитесь к предыдущему сообщению, чтобы узнать о простейшем подходе к решению проблемы.
Временная сложность: O(NlogN)
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход можно оптимизировать на основе следующих наблюдений:

  • Можно заметить, что в каждой операции сумма массива остается неизменной. Следовательно, если сумма массива не делится на N , то невозможно сделать все элементы массива равными.
  • В противном случае каждый элемент массива будет равен сумме массива, деленной на N , скажем, k .
  • Поэтому идея состоит в том, чтобы перебрать массив и найти абсолютную разницу между текущим элементом и k и добавить к ans .
  • Так как в каждой операции и инкременты, и декременты выполняются вместе, ans / 2 — это количество требуемых операций.

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

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

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

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

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