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 intusing 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 codeint 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 Kclass 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 codepublic 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 Kusing 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 codepublic 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 codevar 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!
