C++를 사용하여 합이 n인 최소 거듭제곱 항 수입니다.

문제 설명

두 개의 양의 정수 N과 X가 주어집니다. 작업은 X의 거듭제곱 수가 최소가 되도록 N을 X의 거듭제곱의 합(X0 + X1 +…..+ Xn)으로 표현하는 것입니다.

합을 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