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

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

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

Примеры:

Input: arr[] = {5, 8, 11}, K = 3
Output: 1
Explanation:
Operation 1: Subtract 3 from arr[2](=11) and add 3 to arr[0](=5).
Now, all the elements of the array arr[] are equal.

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

Подход : Эту проблему можно решить с помощью жадного алгоритма. Сначала проверьте, делится ли сумма всех элементов массива arr[] на N или нет. Если он не делится, это означает, что невозможно сделать все элементы массива arr[] равными. В противном случае попробуйте добавить или вычесть значение K , чтобы каждый элемент был равен сумме arr[] / N. Выполните следующие шаги, чтобы решить эту проблему:

  • Инициализируйте переменную sum как 0 , чтобы сохранить сумму всех элементов массива arr[] .
  • Выполните итерацию в диапазоне [0, N-1], используя переменную i , и обновите сумму как sum + arr[i].
  • Если сумма %N не равна 0, то выведите -1 и вернитесь.
  • Инициализируйте переменную valueAfterDivision как sum/N , чтобы сохранить это большое значение, каждый элемент массива arr[] хранится и считается равным 0 , чтобы сохранить минимальное количество операций, необходимых для того, чтобы сделать все элементы массива равными.
  • Выполните итерацию в диапазоне [0, N-1], используя переменную i:
    • Если abs of valueAfterDivision – arr[i] % K не равно 0, то выведите -1 и вернитесь.
    • Обновить количество как количество + абс значенияAfterDivision – обр[i] / К.
  • После выполнения вышеуказанных шагов выведите в качестве ответа count/2 .

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

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

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