Минимальное количество декрементов на 1, необходимое для уменьшения всех элементов кругового массива до 0
Для данного кругового массива arr[] , состоящего из N целых чисел, задача состоит в том, чтобы найти минимальное количество операций, чтобы уменьшить все элементы кругового массива до 0 . В каждой операции уменьшаем текущий элемент на 1 ( начиная с первого элемента ) и переходим к следующему элементу.
Примеры:
Input: arr[] = {2, 0, 2}
Output: 6
Explanation:
Following are the operations performed:
- Reduce the array element arr[0] by 1 modifies the array to {1, 0, 2} and move to the next element arr[1].
- Do nothing and move to the next element i.e., arr[2].
- Reduce the array element arr[2] by 1 modifies the array to {1, 0, 1} and move to the next element arr[0].
- Reduce the array element arr[0] by 1 modifies the array to {0, 0, 1} and move to the next element arr[1].
- Do nothing and move to the next element i.e., arr[2].
- 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)