Проверьте, можно ли получить N из 0, используя не более X приращений и не более Y операций удвоения.

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

Даны три целых числа N , X и Y , задача состоит в том, чтобы проверить, можно ли получить N из 0 , используя следующие операции:

  • Текущее целое число можно увеличить на единицу (т. е. x = x + 1), и это можно сделать не более X раз .
  • Удвойте текущее целое число (т. е. x = 2 * x), и это можно сделать не более Y раз .

Вернуть false, если номер недоступен.

Примеры:

Input: N = 24, X = 6 ,Y = 2
Output: true
Explanation: Initially, a = 0
Increment once so a = 1
Increment once so a = 2
Increment once so a = 3
Increment once so a = 4
Increment once so a = 5
Increment once so a = 6
Double once so a = 12
Double again so a = 24

Input: N = 4, X = 2 ,Y = 0
Output: false

Подход: Вопрос также можно рассмотреть в прямо противоположном сценарии, где N дано, и нам нужно уменьшить его до 0, используя две операции:

  • Деление цели на 2 столько раз, сколько maxDoubles раз
  • Уменьшение цели на 1 столько раз, сколько maxadd раз.

Используйте рекурсивную функцию таким образом, чтобы проверить, можно ли получить 0 или нет. В каждом рекурсивном сценарии уменьшите 1 и снова вызовите функцию. И если число четное, разделите его на 2 и вызовите рекурсивную функцию. Если 0 может быть получено в пределах заданного лимита ходов, вернуть true. В противном случае вернуть ложь.

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


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

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