C++のnのすべての除数で最大の桁数の合計を求めます

この問題では、整数nが与えられます。私たちのタスクは、nのすべての除数で最大の桁の合計を見つけることです。

問題の説明： ここでは、桁の合計が最大である数nの約数を見つけます。

問題を理解するために例を見てみましょう。

入力： 18

出力： 9

説明：

18の約数はすべて1、2、3、6、9、18です。

最大桁数の合計は9です。

ソリューションアプローチ

数値Nのすべての除数を見つけます。次に、各除数の桁の合計を見つけて、合計が最大の値を返します。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;

int calcDigitSum(int n) {
   
   int sum = 0;
   while (n != 0) {
      sum = sum + n % 10;
      n = n/10;
   }
   return sum;
}

int largestDigitSumdivisior(int n) {
   
   int maxSum = 0;
   for (int i = 1; i <= n; i++)
      if (n % i == 0)
      maxSum = max(maxSum, calcDigitSum(i));

   return maxSum;
}

int main() {
   
   int n = 45;
   cout<<"The divisor with largest sum of digits is "<<largestDigitSumdivisior(n)<<endl;
   return 0;
}

出力

The divisor with largest sum of digits is 9

除数を見つけるためにメソッドを変更し、それをより効果的にすることで、ソリューションをより効果的にすることができます。

この問題では、sqrt（n）まで反復し、すべての除数と他の約数がn/divを使用して計算されていることを確認します。これにより、sqrt（n）の除数を見つけるための時間計算量が削減されます。

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;

int calcDigitSum(int n) {
   
   int sum = 0;
   while (n != 0) {
      sum = sum + n % 10;
      n = n / 10;
   }
   return sum;
}

int largestDigitSumdivisior(int n) {
   
   int maxSum = 0;
   for (int i = 1; i*i <= n; i++) {

      if (n % i == 0) {
         maxSum = max(maxSum, calcDigitSum(i));
         maxSum = max(maxSum,calcDigitSum(n/i));
      }  
   }
   return maxSum;
}

int main() {
   
   int n = 32;
   cout<<"The divisor with largest sum of digits is "<<largestDigitSumdivisior(n)<<endl;
   return 0;
}

出力

The divisor with largest sum of digits is 8