Given two positive integers N and K. The task is to find the Kth number that can be written as the sum of different non-negative powers of N.
Examples:
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
Approach: This problem can be solved by using the concept of decimal to binary conversion. The idea is to find the binary representation of K and start iterating from the least significant bit to the most significant bit. If the current bit is set then include the corresponding power of N to the answer otherwise skip that bit. Refer to the picture below for a better understanding.
Example: When N = 3, K = 9
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find Kth number that can be// represented as sum of different// non-negative powers of Nint FindKthNum(int n, int k){ // To store the ans int ans = 0; // Value of current power of N int currPowOfN = 1; // Iterating through bits of K // from LSB to MSB while (k) { // If the current bit is 1 then include // corresponding power of n into ans if (k & 1) { ans = ans + currPowOfN; } currPowOfN = currPowOfN * n; k = k / 2; } // Return the result return ans;}// Driver Codeint main(){ int N = 3; int K = 4; cout << FindKthNum(N, K);} |
Java
// Java program for the above approachclass GFG{ // Function to find Kth number that can be // represented as sum of different // non-negative powers of N static int FindKthNum(int n, int k) { // To store the ans int ans = 0; // Value of current power of N int currPowOfN = 1; // Iterating through bits of K // from LSB to MSB while (k > 0) { // If the current bit is 1 then include // corresponding power of n into ans if ((k & 1) == 1) { ans = ans + currPowOfN; } currPowOfN = currPowOfN * n; k = k / 2; } // Return the result return ans; } // Driver Code public static void main(String []args) { int N = 3; int K = 4; System.out.println(FindKthNum(N, K)); }}// This Code is contributed by ihritik |
Python3
# Python program for the above approach# Function to find Kth number that can be# represented as sum of different# non-negative powers of Ndef FindKthNum(n, k): # To store the ans ans = 0 # value of current power of N currPowOfN = 1 # Iterating through bits of K # from LSB to MSB while (k > 0): # If the current bit is 1 then include # corresponding power of n into ans if ((k & 1) == 1) : ans = ans + currPowOfN currPowOfN = currPowOfN * n k = k // 2 # Return the result return ans# Driver CodeN = 3K = 4print(FindKthNum(N, K)); # This Code is contributed by ihritik |
C#
// C# program for the above approachusing System;class GFG{ // Function to find Kth number that can be // represented as sum of different // non-negative powers of N static int FindKthNum(int n, int k) { // To store the ans int ans = 0; // Value of current power of N int currPowOfN = 1; // Iterating through bits of K // from LSB to MSB while (k > 0) { // If the current bit is 1 then include // corresponding power of n into ans if ((k & 1) == 1) { ans = ans + currPowOfN; } currPowOfN = currPowOfN * n; k = k / 2; } // Return the result return ans; } // Driver Code public static void Main() { int N = 3; int K = 4; Console.WriteLine(FindKthNum(N, K)); }}// This Code is contributed by ihritik |
Javascript
<script>// JavaScript program for the above approach// Function to find Kth number that can be// represented as sum of different// non-negative powers of Nfunction FindKthNum(n, k){ // To store the ans let ans = 0; // Value of current power of N let currPowOfN = 1; // Iterating through bits of K // from LSB to MSB while (k) { // If the current bit is 1 then include // corresponding power of n into ans if (k & 1) { ans = ans + currPowOfN; } currPowOfN = currPowOfN * n; k = Math.floor(k / 2); } // Return the result return ans;}// Driver Codelet N = 3;let K = 4;document.write(FindKthNum(N, K));// This code is contributed by rohitsingh07052.</script> |
9
Time Complexity: O(log2K)
Space Complexity: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
