1.
Introduction
2.
The Problem Statement
2.1.
Example
3.
Approach
3.1.
Algorithm
3.2.
Program
3.3.
Input
3.4.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Key Takeaways
Last Updated: Mar 27, 2024

# Find Kth Number, Which can be Written as the Sum of Powers of ‘N’

Ujjawal Gupta
0 upvote

## Introduction

One day, ninja's teacher gave him an assignment in which he had to calculate the Kth number which can be written as the sum of powers of ‘N’. Help ninja to pass the assignment.

The above problem is the standard Bit Manipulation problem. Bit Manipulation based-coding problems are widely asked in coding contests and various coding interviews.

This blog will solve the above problem using the bit manipulation approach.

## The Problem Statement

You are given an integer ‘N’ and ‘K’. Your task is to find the Kth number, which can be written as the sum of different positive(or zero) powers of ‘N’.

### Example

Let N = 2, and K = 3, then the 1st number as the sum of powers of ‘N’ is 1 (2^0), 2nd number is 2 (2^1), and 3rd number is 3 (2 ^ 0 + 2 ^ 1).

Also see, Euclid GCD Algorithm

## 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:
• P = P * N;
• K = K / 2;
• 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.

// Create variable to store the current value.
int p = 1;
while (k)
{

// If the bit is set.
if (k % 2 == 1)
{
}
p = p * n;
k /= 2;
}
}
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!

Live masterclass