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

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

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

Примеры:

Input: arr[] = {1, 0, 5}
Output: 3
Explanation:
Operation 1: Subtract arr[2](= 5) by 1 and add it to arr[1](= 0). Therefore, the array arr[] modifies to {1, 1, 4}.
Operation 2: Subtract arr[2](= 4) by 1 and add it to arr[1](= 1). Therefore, the array arr[] modifies to {1, 2, 3}.
Operation 3: Subtract arr[2](= 3) and arr[1](= 2) by 1 and add it to arr[1](= 1) and arr[2](= 2) respectively. Therefore, the array arr[] modifies to {2, 2, 2}.

Therefore, the minimum number of operations required is 3.

Input: arr[] = {0, 3, 0}
Output: 2

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

  • Все элементы массива можно сделать равными тогда и только тогда, когда значение всех элементов массива равно среднему значению массива.
  • Поскольку из элемента массива за раз можно вычесть только 1 , минимальное количество ходов равно максимуму суммы префиксов массива или количеству ходов, необходимых для того, чтобы сделать каждый элемент равным среднему значению массива.

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

  • Вычислите сумму элементов массива arr[] , скажем, S .
  • Если сумма S не делится на N , то выведите «-1» .
  • В противном случае выполните следующие операции:
    • Сохраните среднее значение элементов массива в переменной, скажем, avg .
    • Инициализируйте две переменные, скажем, total и count с 0 , чтобы сохранить требуемый результат и сумму префикса минимальных ходов для достижения avg соответственно.
    • Пройдите по заданному массиву arr[] и выполните следующие шаги:
      • Добавьте значение (arr[i] – avg) к count .
      • Обновите значение total до максимального абсолютного значения count , total , (arr[i] – avg) .
  • После выполнения вышеуказанного шага напечатайте значение total как результирующую минимальную требуемую операцию.

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

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

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