Найдите K-е число, которое можно записать в виде суммы различных степеней N
Данный два положительных целых числа 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)