Найдите K-е число, которое можно записать в виде суммы различных степеней N

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

Данный два положительных целых числа N и K . Задача состоит в том, чтобы найти K -е число, которое можно записать в виде суммы различных неотрицательных степеней N .

Примеры:

Input: N = 3, K = 4
Output: 9
Explanation:
First number that can be written as sum of powers of 3 is [1 = 30]
Second number that can be written as sum of powers of 3 is [3 = 31]
Third number that can be written as sum of powers of 3 is [4 = 30 + 31]
Fourth number that can be written as sum of powers of 3 is [9 = 32]
Therefore answer is 9.

Input: N = 2, K = 12
Output: 12

Подход: Эту проблему можно решить, используя концепцию преобразования десятичных чисел в двоичные. Идея состоит в том, чтобы найти двоичное представление K и начать итерацию от младшего бита к старшему биту. Если текущий бит установлен, тогда включите соответствующую степень N в ответ, в противном случае пропустите этот бит. Обратитесь к картинке ниже для лучшего понимания.

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

Временная сложность: O (log 2 K)

Космическая сложность: O(1)

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