Количество итераций, чтобы сделать его минимальным, равным 0, путем вращения массива с последующим уменьшением его от исходного массива.

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

Примеры:

Input: arr[] = { 2, 6, 3, 4, 8, 7 }
Output: 3
Explanation: Refer to the image below for explanation.

Input: arr[] = { 4, 10, 12, 3, 9, 7 }
Output: 5

Наивный подход: самый простой способ решить эту проблему — использовать жадный подход.

• Просто извлеките первый элемент массива и добавьте его в конец, а затем выполните вычитание соответствующего элемента.
• Точно так же выполните ту же операцию с результирующим массивом, пока мы не получим минимальный элемент в массиве как ноль и не вернем количество итераций.

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

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

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

• Сохраните первый элемент массива в переменной x .
• Теперь найдите абсолютную разницу между последовательными элементами.
• Заменить результат с индекса 0 .
• Вычтите последний элемент из переменной x и сохраните его.
• подсчитайте итерацию и повторите шаги.
• Возврат считается окончательным ответом.

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

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