Approach
The above problem can be solved using the concept of bit manipulation. Iterate all the bits of ‘K’ and check whether the bit is set or not. If it is, then include the corresponding answer for power of ‘N’ in the final answer. For example, suppose N = 3 and K = 9. The binary representation of K is 1001. Here, the 0th and 3rd bits are set which contributes 3^0 and 3^3 respectively. Hence our answer is 3^0 + 3^3 = 28. We are doing this because if any bit of ‘K’ is set then including that bit in the answer means our answer corresponding to that bit is calculated.
The algorithm of the approach is discussed below.
Algorithm
-
Define a function ‘getKthNumber()’, which takes two arguments ‘N’ and ‘K’. perform following operations:
- Declare a variable ‘ANSWER’ and initialize it to 0.
- Declare a variable ‘P’ and initialize it to 1.
-
while(K):
- If K % 2 == 1:
- ANSWER += P;
- P = P * N;
- K = K / 2;
- Return ‘ANSWER’.
- Call the above function in the main function and pass ‘N’ and ‘K’.
Program
#include <iostream>
using namespace std;
// Function definition.
int getKthNumber(int n, int k)
{
// Create variable to store the answer.
int answer = 0;
// Create variable to store the current value.
int p = 1;
while (k)
{
// If the bit is set.
if (k % 2 == 1)
{
answer += p;
}
p = p * n;
k /= 2;
}
return answer;
}
int main()
{
// Input 'N' and 'K'.
int n, k;
cin >> n >> k;
// Function Call.
int ans = getKthNumber(n, k);
cout << ans;
return 0;
}
Input
3 4
Output
9
Time Complexity
O(log(K)), where ‘K’ is the given K-th number. There is total log(K) bits in ‘K’ and we are accessing each bits. Hence, its time complexity is O(log(K)).
Space Complexity
O(1).
As we don’t use extra space except for a few variables.
Key Takeaways
In this blog, we have learned how to calculate the Kth number, which can be written as the sum of powers of ‘N’. We have discussed the efficient approach. Here, we have seen how we can use the concept of bit manipulation to achieve the result.
Therefore learning never stops, and there is a lot more to learn.
Check out this problem - Two Sum Problem
So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!
305+ registered