Проверить, можно ли сделать Array строго возрастающим, сдвинув на 1 значение вправо

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

Примечание. Целое число в любом индексе после любой операции не должно быть отрицательным.

Пример:

Input: arr[] = {4, 5, 4}
Output: Yes
Explanation: The array can be made strictly increasing by performing the following operations:

• Choose i = 1 and shift value 1 from A₁ to A₂ . Now, arr[] = {3, 6, 4}.
• Choose i = 2 and shift value 1 from A₂ to A₃ . Now, arr[] = {3, 5, 5}.
• Choose i = 2 and shift value 1 from A₂ to A₃ . Now, arr[] = {3, 4, 6}.

Input: arr[] = {0, 1, 0}
Output: No

Подход: Данную задачу можно решить с помощью жадного подхода. Идея состоит в том, что для любого индекса i наименьшая возможная строго возрастающая последовательность без включения отрицательных целых чисел равна 0, 1, 2, 3, … . Следовательно, для каждого значения i в диапазоне [0, N) сумма целых чисел до arr[i] должна быть больше суммы ряда 0, 1, 2, …, i-1 , что эквивалентно ( я * (я – 1))/2 . Следовательно, если данный массив удовлетворяет этому условию, верните « Да », в противном случае верните « Нет ».

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

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