Минимум прыжков для прохождения всех целых чисел в диапазоне [1, N], таких что целое число i может перепрыгнуть на i шагов
Для заданного целого числа N задача состоит в том, чтобы найти минимальное количество шагов для посещения всех целых чисел в диапазоне [1, N] , выбрав любое целое число и совершив i -й шаг на каждом i -м прыжке.
Примечание. Можно вернуться к целому числу более одного раза.
Примеры:
Input: N = 6
Output: 3
Explanation:
One of the following way is:
First start at first number and visit the integers {1, 2, 4}.
Now start at 2nd number and visit the integers as {2, 3, 5}
Now start at the last number and visit it.
Therefore, in total of 3 steps one can visit all the numbers in the range [1, 6]. And also it is the minimum number of steps needed.Input: N = 4
Output: 2
Наивный подход: Данная проблема может быть решена на основе следующих наблюдений:
- In each step the sizes of jumps increases therefore some numbers remains unvisited in a step.
- Starting from the first number and performing the jumps it can be observed that the maximum size of the jump is the total number of steps needed to visit every number. As in one move, one cannot visit each number between two unvisited numbers.
Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте две переменные, скажем, count = 1 и res = 0.
- Пройдите через диапазон [1, N] и увеличьте i на count и обновите res как res =max(res, count) и увеличьте count на 1 .
- После выполнения вышеуказанных шагов распечатайте файл res.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(1)
Эффективный подход. Описанные выше шаги можно оптимизировать на основе следующих наблюдений:
- Suppose an array arr[] as arr[] ={1, 1, 2, 2, 2, 3, 3, 3, ….]. Now the idea is to find the number K which is the maximum size of jump taken in a step.
- In above taken array, Since, 1 occurs twice, 2 occurs thrice, 3 occurs four times and so on. (K – 1) would occur K times.
- Now let K occurs c times, then count of total occurrence must be equal to N.
- 2 + 3 + 4 +….+ K + c = N
- c = N – 2 – 3 – 4 -….- K …..(i)
- Then one need to find the greatest K satisfying equation (i) also c≥1, then
- K2 + K – 2 × N ≤ 0.
- Therefore, K = (-1 + √(1 + 8 ×N)) / 2
Выполните следующие шаги, чтобы решить проблему:
- Выведите значение (-1 + √(1 + 8 *N)) / 2 .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (1)
Вспомогательное пространство: O(1)