Минимизируйте прыжки, чтобы достичь X, прыгая на K позиций или на 1 позицию.

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

Учитывая два значения X и K , задача состоит в том, чтобы минимизировать количество прыжков, чтобы достичь X из 0 , перепрыгивая K позиций или 1 позицию за раз.

Пример:

Input: N = 5, K = 2
Output: 3
Explanation: First two jumps of K = 2 steps and 
third jump of 1 step will be required

Input: N = 3, K = 5
Output: 3
Explanation: First two jumps of 1 step will be required 
and the third jump will be of 3 positions. Or
Use two jumps of 3 spositions to reach 6 and 
then jump 1 position on left to reach 5
 

Подход: Задача может быть решена на основе следующей математической идеи:

To minimize the steps, it is optimal to cover as much distance as possible using jumps of K positions. Say N and M are the two multiples of K that are closest to X (N ≤ X and M > X).

So steps required to reach X can be:

  • S1 = N/K + (X – N)
  • S2 = M/K + (M – X)

The minimum number of steps = minimum between S1 and S2

Выполните шаги, указанные ниже, чтобы решить проблему:

  • Получите значения S1 и S2.
  • Найдите минимум между ними.
  • Верните минимальное значение в качестве ответа.

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

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

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