Минимальное количество декрементов на 1, необходимое для уменьшения всех элементов кругового массива до 0

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

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

Примеры:

Input: arr[] = {2, 0, 2}
Output: 6
Explanation:
Following are the operations performed:

  1. Reduce the array element arr[0] by 1 modifies the array to {1, 0, 2} and move to the next element arr[1].
  2. Do nothing and move to the next element i.e., arr[2].
  3. Reduce the array element arr[2] by 1 modifies the array to {1, 0, 1} and move to the next element arr[0].
  4. Reduce the array element arr[0] by 1 modifies the array to {0, 0, 1} and move to the next element arr[1].
  5. Do nothing and move to the next element i.e., arr[2].
  6. Reduce the array element arr[2] by 1 modifies the array to {0, 0, 0} and move to the next element arr[0].

After the above operations, all the array elements of the circular array has been reduced to 0. Therefore, the minimum number of operations required is 6.

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

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы пройти по заданному массиву в циклическом порядке, выполняя заданные операции до тех пор, пока все элементы массива не станут равными 0 , и отслеживать количество выполненных операций. После выполнения вышеуказанных шагов выведите количество выполненных операций.

Временная сложность: O(N*M), где M — максимальный элемент массива .
Вспомогательное пространство: O(1)

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

  • Инициализируйте две переменные, скажем, pos и M , которые хранят последний индекс максимального элемента и максимального элемента соответственно.
  • Пройдите по данному массиву, используя переменную i , и если значение arr[i] не меньше M , измените значение M как arr[i] и pos как i .
  • После выполнения вышеуказанных шагов выведите значение (mx – 1)*N + pos +1 как результирующее минимальное количество шагов.

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

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

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