Given two positive integer n and x. The task is to express n as sum of powers of x (xa1 + xa2 +…..+ xa3) such that the number of powers of x (xa1, xa2, ….., xa3) should be minimum. Print the minimum number of power of x used to make sum equal to n.
Examples:
Input : n = 5, x = 3
Output : 3
5 = 30 + 30 + 31.
We use only 3 power terms of x { 30, 30, 31}
Input : n = 13, x = 4
Output : 4
13 = 40 + 41 + 41 + 41.
We use only four power terms of x.
Input : n = 6, x = 1
Output : 6
If x = 1, then answer will be n only (n = 1 + 1 +…. n times).
The idea is to use Horner’s method. Any number n can be expressed as, n = x * a + b where 0 <= b <= x-1. Now since b is between 0 to x – 1, then b should be expressed as sum of x0 b times.
Further a can be decomposed in similar manner and so on.
Algorithm to solve this problem:
1. Initialize a variable ans to 0. 2. While n > 0 a) ans = ans + n % x b) n = n/x 3. Return ans.
Below is the implementation of above idea :
C++
// C++ program to calculate minimum number // of powers of x to make sum equal to n. #include <bits/stdc++.h> using namespace std; // Return minimum power terms of x required int minPower(int n, int x) { // if x is 1, return n since any power // of 1 is 1 only. if (x==1) return n; // Consider n = a * x + b where a = n/x // and b = n % x. int ans = 0; while (n > 0) { // Update count of powers for 1's added ans += (n%x); // Repeat the process for reduced n n /= x; } return ans; } // Driven Program int main() { int n = 5, x = 3; cout << minPower(n, x) << endl; return 0; } |
Java
// Java program to calculate // minimum numberof powers of // x to make sum equal to n. class GFG { // Return minimum power // terms of x required static int minPower(int n, int x) { // if x is 1, return n since // any power of 1 is 1 only. if (x==1) return n; // Consider n = a * x + b where // a = n/x and b = n % x. int ans = 0; while (n > 0) { // Update count of powers // for 1's added ans += (n % x); // Repeat the process for reduced n n /= x; } return ans; } // Driver code public static void main (String[] args) { int n = 5, x = 3; System.out.println(minPower(n, x)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to # calculate minimum number # of powers of x to make # sum equal to n. # Return minimum power # terms of x required def minPower(n,x): # if x is 1, return # n since any power # of 1 is 1 only. if (x==1): return n # Consider n = a * x + b where a = n/x # and b = n % x. ans = 0 while (n > 0): # Update count of powers for 1's added ans += (n%x) # Repeat the process for reduced n n //= x return ans # Driver code n = 5 x = 3print(minPower(n, x)) # This code is contributed # by Anant Agarwal. |
C#
// C# program to calculate // minimum numberof powers // of x to make sum equal // to n. using System; class GFG { // Return minimum power // terms of x required static int minPower(int n, int x) { // if x is 1, return n since // any power of 1 is 1 only. if (x == 1) return n; // Consider n = a * x + b where // a = n / x and b = n % x. int ans = 0; while (n > 0) { // Update count of // powers for 1's // added ans += (n % x); // Repeat the process // for reduced n n /= x; } return ans; } // Driver code public static void Main () { int n = 5, x = 3; Console.WriteLine(minPower(n, x)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to calculate minimum number // of powers of x to make sum equal to n. // Return minimum power // terms of x required function minPower($n, $x) { // if x is 1, return n since // any power of 1 is 1 only. if ($x == 1) return $n; // Consider n = a * x + b // where a = n/x and b = n % x. $ans = 0; while ($n > 0) { // Update count of powers // for 1's added $ans += ($n % $x); // Repeat the process // for reduced n $n /= $x; } return $ans; } // Driver Code $n = 5; $x = 3; echo(minPower($n, $x)); // This code is contributed by Ajit. ?> |
Javascript
<script> // JavaScript program to calculate minimum number // of powers of x to make sum equal to n. // Return minimum power terms of x required function minPower(n, x) { // if x is 1, return n since any power // of 1 is 1 only. if (x==1) return n; // Consider n = a * x + b where a = n/x // and b = n % x. let ans = 0; while (n > 0) { // Update count of powers for 1's added ans += (n%x); // Repeat the process for reduced n n = Math.floor(n / x); } return ans; } // Driven Program let n = 5, x = 3; document.write(minPower(n, x) + "<br>"); // This code is contributed by Surbhi Tyagi. </script> |
Output:
3
Time complexity: O(logxn)
Auxiliary space:O(1)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
