Преобразуйте X в Y, многократно умножая X на 2 или добавляя 1 в конце

Даны два положительных целых числа X и Y , задача состоит в том, чтобы проверить, возможно ли преобразовать число X в Y , умножив X на 2 или добавив 1 в конце X . Если можно преобразовать X в Y , то выведите «Да» . В противном случае выведите «Нет» .

Примеры:

Input: X = 100, Y = 40021
Output: Yes
Explanation:
Below are the operations performed to convert X into Y:
Operation 1: Multiply X(= 100) by 2, modifies the value X to 200.
Operation 2: Append 1 at the end of X(= 200), modifies the value X to 2001.
Operation 3: Multiply X(= 2001) by 2, modifies the value X to 4002.
Operation 4: Append 1 at the end of X(= 4002), modifies the value X to 40021.
Therefore, from the above operations, it can be seen that the value X can be converted into Y. Hence, print Yes.

Input: X = 17 and Y = 35
Output: No

Подход: Данную задачу можно решить, выполнив операции в обратном порядке, т.е. попытаться преобразовать значение Y в X . Выполните следующие шаги, чтобы решить проблему:

• Повторяйте до тех пор, пока значение Y не станет больше, чем X , и выполните следующие шаги:
  • Если значение последней цифры Y равно 1, то разделите значение Y на 10 .
  • В противном случае, если значение Y делится на 2, разделите Y на 2 .
  • В противном случае вырваться из цикла.
• После выполнения вышеуказанных шагов, если значение Y совпадает со значением X , выведите Yes . В противном случае выведите Нет .

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

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