Проверить, может ли число N быть представлено в виде суммы степеней X или нет

Даны два положительных числа N и X , задача состоит в том, чтобы проверить, может ли данное число N быть выражено как сумма различных степеней X. Если найдено, что это правда, то выведите «Да» , иначе выведите «Нет» .

Примеры:

Input: N = 10, X = 3
Output: Yes
Explanation:
The given value of N(= 10) can be written as (1 + 9) = 3⁰ + 3². Since all the power of X(= 3) are distinct. Therefore, print Yes.

Input: N= 12, X = 4
Output: No

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

• Повторяйте цикл до тех пор, пока значение N не станет не менее 0 , и выполните следующие шаги:
  • Вычислите значение остатка rem при делении N на X .
  • Если значение rem не меньше 2 , то выведите «No» и вернитесь.
  • В противном случае обновите значение N как N / X .
• После выполнения вышеуказанных шагов, если никакого завершения не существует, выведите «Да» , так как результат в N может быть выражен в различной степени X .

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

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