Проверьте, можно ли получить N из 0, используя не более X приращений и не более Y операций удвоения.
Даны три целых числа 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 = 24Input: N = 4, X = 2 ,Y = 0
Output: false
Подход: Вопрос также можно рассмотреть в прямо противоположном сценарии, где N дано, и нам нужно уменьшить его до 0, используя две операции:
- Деление цели на 2 столько раз, сколько maxDoubles раз
- Уменьшение цели на 1 столько раз, сколько maxadd раз.
Используйте рекурсивную функцию таким образом, чтобы проверить, можно ли получить 0 или нет. В каждом рекурсивном сценарии уменьшите 1 и снова вызовите функцию. И если число четное, разделите его на 2 и вызовите рекурсивную функцию. Если 0 может быть получено в пределах заданного лимита ходов, вернуть true. В противном случае вернуть ложь.
Ниже приведена реализация вышеуказанного подхода:
Сложность времени: НА)
Вспомогательное пространство: O(1)