Tìm tổng các chữ số lớn nhất trong tất cả các ước của n trong C ++

Trong bài toán này, chúng ta được cung cấp một số nguyên n. Nhiệm vụ của chúng ta là tìm tổng các chữ số lớn nhất trong tất cả các ước của n.

Mô tả sự cố: Ở đây, chúng ta sẽ tìm ước của số n có tổng các chữ số lớn nhất.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: 18

Đầu ra: 9

Giải thích:

Tất cả các ước của 18 là 1, 2, 3, 6, 9, 18.

Tổng các chữ số tối đa là 9.

Phương pháp tiếp cận giải pháp

Tìm tất cả các ước của số N. Và sau đó tìm tổng các chữ số của mỗi ước rồi trả về giá trị có tổng lớn nhất.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

The divisor with largest sum of digits is 9

Giải pháp có thể được thực hiện hiệu quả hơn bằng cách sử dụng sửa đổi phương pháp để tìm số chia và làm cho nó hiệu quả hơn.

Trong bài toán này, chúng ta sẽ lặp lại cho đến sqrt (n) và tìm tất cả các ước và các ước khác được tính bằng cách sử dụng n / div. Điều này làm giảm độ phức tạp về thời gian để tìm các ước số cho sqrt (n).

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

The divisor with largest sum of digits is 8