使用C ++，总和等于n的最小幂项数量。

问题陈述

给定两个正整数N和X。任务是将N表示为X的幂之和（X0 + X1 +….. + Xn），这样X的幂应为最小。

打印用于使总和等于N的N的最小乘方数。

如果N = 15且X = 3，则我们需要3的3的幂，如下所示-

15 =（3 ² + 3 ¹ + 3 ¹）

算法

使用以下公式计算最终结果-

1. If x = 1, then answer will be n only (n = 1 + 1 +…. n times)s
2. 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

示例

#include <iostream>
using namespace std;
int minNumOfPower(int n, int x){
   if (x == 1) {
      return n;
   }
   int result = 0;
   while (n > 0) {
      result = result + (n % x);
      n = n / x;
   }
   return result;
}
int main(){
   int n = 15;
   int x = 3;
   cout << "Minimum number of powers = " <<
   minNumOfPower(15, 3) << endl;
   return 0;
}

输出结果

当您编译并执行上述程序时。它生成以下输出-

Minimum number of powers = 3