หาผลรวมตัวเลขสูงสุดของตัวหารทั้งหมดของ n ใน C++

โจทย์

ได้รับจำนวนเต็ม n ทางเราต้อง หาผลรวมตัวเลขสูงสุดในตัวหารทั้งหมดของ n

ตัวอย่าง

Input: 18

Output: 9

อธิบาย: ตัวหารของ 18: 1,2,3,6,9,18 -> ผลรวมตัวเลขสูงสุดคือ 9 (จาก 9 และ 18)

แนวทางแก้ปัญหา

วิธีแบบง่าย: วนหาตัวหารทุกตัว คำนวณผลรวมตัวเลข หาค่าสูงสุด

วิธีที่ดีกว่า (O(√n)): วนแค่ถึง √n หาตัวหารคู่ (i และ n/i) พร้อมกัน

โปรแกรมตัวอย่าง (วิธีที่ดีกว่า)

#include <iostream>
using namespace std;

int calcDigitSum(int n) {
    int sum = 0;
    while (n != 0) { sum += n % 10; 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