和等于n的最小幂项数-yiteyi-C++库

给定两个正整数 N 和十、 .任务是将n表示为x（x）的幂和 ^a1 +x ^a2 +…..+ 十、 ^a3 )这样x（x）的幂次数 ^a1 十、 ^a2 , ….., 十、 ^a3 )应该是最低限度的。打印用于使总和等于n的x的最小幂数。例如：

null

Input : n = 5, x = 3Output : 35 = 3⁰ + 3⁰ + 3¹.We use only 3 power terms of x { 3⁰, 3⁰, 3¹} Input : n = 13, x = 4Output : 413 = 4⁰ + 4¹ + 4¹ + 4¹.We use only four power terms of x.Input : n = 6, x = 1Output : 6

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

如果x=1，则答案将仅为n（n=1+1+..n次）。这个想法是使用霍纳法 .任何数字n都可以表示为n=x*a+b，其中0<=b<=x-1。既然b在0到x–1之间，那么b应该表示为x的和 ⁰ b次。此外，a可以以类似的方式分解，等等。解决此问题的算法：

1. Initialize a variable ans to 0.2. While n > 0   a) ans = ans + n % x   b) n = n/x3. Return ans.

以下是上述理念的实施：

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                                     =                                     3                       
                         print                                     (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>                       

输出：

本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章