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

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

Дан массив arr[]. Задача состоит в том, чтобы минимизировать количество операций, необходимых для того, чтобы сделать все элементы в arr[] равными. Разрешается заменить любой элемент в arr[] любым другим элементом почти один раз. Найдите минимальное количество операций, необходимых для этого, за одну операцию возьмите любой суффикс arr[] и увеличьте/уменьшите значения в этом суффиксе на 1 .

Примеры

Input: arr[] = {-1, 0, 2}
Output: 1
Explanation: Following are the operations done to make all the elements in arr[] to be equal. 
Initially, change the last element of array to 0, so arr[] = {-1, 0, 0}
Now, using the operation once on the suffix starting at arr2, which means arr2 and arr3 are decreased by 1 . Thus, making all elements of array -1.
Hence, the number of operations is 1. 

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

Подход : Эта проблема основана на реализации. Выполните следующие шаги, чтобы решить данную проблему.

  • Поскольку не требуется выполнять какие-либо операции с суффиксом, начинающимся с arr 1 , поскольку это может изменить все целые числа в массиве.
  • Итак, единственный способ сделать arr i равным arr i-1 заключается в выполнении операции над суффиксом, начиная с a i , abs(a i −a i-1 ) раз.
  • Теперь оптимальным способом первоначального изменения значения в массиве является минимизация операций.
  • Чтобы сделать arr 1 равным arr 2 , минимальные операции уменьшаются на abs (arr 2 – arr 1 ) .
  • Точно так же, чтобы сделать arr n равным arr n-1 , operation = abs(arr n – arr n-1 ) .
  • Для левых элементов изменение любого элемента arr i , влияет как на abs(a i −a i-1 ), так и на abs(a i+1 −a i ) .
  • Кроме того, обратите внимание на тот важный факт, что это значение минимизируется, когда i находится между i-1 и i+1 включительно.
  • Таким образом, число операций уменьшается с abs(a i −a i-1 )+abs(a i+1 −a i ) до abs(a i+1 −a i-1 ) .
  • Верните окончательный ответ.

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

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

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