Given two positive integers N and K, the task is to find the minimum number to be added to N to make it a power of K.
Examples:
Input: N = 9, K = 10
Output: 1
Explanation:
9 + 1 = 10 = 101
Input: N = 20, K = 5
Output: 5
Explanation:
20 + 5 = 25 = 52
Approach: The idea to solve this problem is to observe that the minimum power of K which can be formed from N is the next greater power of K. So, the idea is to find the next greater power of K and find the difference between N and this number. The next greater power of K can be found by the formula,
Kint(log(N)/log(K)) + 1
Therefore, the minimum number to be added can be computed by:
Minimum Number = Kint(log(N)/log(K)) + 1 – N
Below is the implementation of the above approach:
C++
// C++ program to find the minimum number // to be added to N to make it a power of K #include <bits/stdc++.h> #define ll long long int using namespace std; // Function to return the minimum number // to be added to N to make it a power of K. int minNum( int n, int k) { int x = ( int )( log (n) / log (k)) + 1; // Computing the difference between // then next greater power of K // and N int mn = pow (k, x) - n; return mn; } // Driver code int main() { int n = 20, k = 5; cout << minNum(n, k); return 0; } |
Java
// Java program to find the minimum number // to be added to N to make it a power of K class GFG{ // Function to return the minimum number // to be added to N to make it a power of K. static int minNum( int n, int k) { int x = ( int )(Math.log(n) / Math.log(k)) + 1 ; // Computing the difference between // then next greater power of K // and N int mn = ( int ) (Math.pow(k, x) - n); return mn; } // Driver code public static void main(String[] args) { int n = 20 , k = 5 ; System.out.print(minNum(n, k)); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program to find the minimum number # to be added to N to make it a power of K import math # Function to return the minimum number # to be added to N to make it a power of K. def minNum(n, k): x = int ((math.log(n) / / math.log(k))) + 1 # Computing the difference between # then next greater power of K # and N mn = pow (k, x) - n return mn # Driver code if __name__ = = '__main__' : n = 20 k = 5 print (minNum(n, k)) # This code is contributed by rutvik_56 |
C#
// C# program to find the minimum number // to be added to N to make it a power of K using System; class GFG{ // Function to return the minimum number // to be added to N to make it a power of K. static int minNum( int n, int k) { int x = ( int )(Math.Log(n) / Math.Log(k)) + 1; // Computing the difference between // then next greater power of K // and N int mn = ( int )(Math.Pow(k, x) - n); return mn; } // Driver code public static void Main( string [] args) { int n = 20, k = 5; Console.Write(minNum(n, k)); } } // This code is contributed by Ritik Bansal |
Javascript
<script> // Javascript program to find the minimum number // to be added to N to make it a power of K // Function to return the minimum number // to be added to N to make it a power of K. function minNum(n, k) { var x = parseInt(Math.log(n) / Math.log(k)) + 1; // Computing the difference between // then next greater power of K // and N var mn = Math.pow(k, x) - n; return mn; } // Driver code var n = 20, k = 5; document.write( minNum(n, k)); </script> |
5
Time Complexity: O(log n)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!