Tìm tổng chữ số nhỏ nhất có thể sau khi thêm số d trong C++

Mô tả vấn đề

Trong bài toán này, chúng ta được cho hai số n và d. Nhiệm vụ là tìm tổng chữ số nhỏ nhất có thể đạt được sau khi cộng một bội số của d vào n. Cụ thể, ta cần tối thiểu hóa tổng chữ số bằng cách cộng k lần d vào n.

Ví dụ minh họa

Đầu vào:

n = 5230, d = 54

Đầu ra:

1

Giải thích:

Số sẽ là 5230 + (2*54) = 5338
Tổng chữ số của 5338: 5+3+3+8 = 19 → 1+9 = 10 → 1+0 = 1

Phương pháp giải quyết

Một cách tiếp cận đơn giản là kiểm tra tất cả các bội số của d từ 1 đến 8, vì ở bội số thứ 9, tổng chữ số sẽ lặp lại. Điều này dựa trên modulo 9, nơi mà tổng chữ số của một số tương đương với số đó modulo 9 (trừ khi số chia hết cho 9 thì tổng chữ số là 9). Do đó, (n + d*(9k + l)) % 9 tương đương với (n + d*l) % 9. Vì vậy, ta chỉ cần kiểm tra các bội số l*d với l từ 1 đến 8 và trả về giá trị nhỏ nhất tìm được.

Một tối ưu hóa nhỏ: tổng chữ số không bao giờ nhỏ hơn 1, nên nếu tìm được tổng chữ số = 1, ta có thể trả về ngay lập tức.

Chương trình minh họa

#include <iostream>
using namespace std;

int calcDigitSum(int n) {
    int i = n % 9;
    if (i == 0)
        return 9;
    else
        return i;
}

int findMinDigitSum(int n, int d) {
    int minSum = 10;
    int number;
    for (int i = 1; i < 9; i++) {
        number = (n + i * d);
        minSum = min(minSum, calcDigitSum(number));
        if(minSum == 1)
            return minSum;
    }
    return minSum;
}

int main() {
    int n = 5230, d = 54;
    cout << "Tổng chữ số nhỏ nhất sau khi thêm số là " << findMinDigitSum(n, d);
    return 0;
}

Kết quả đầu ra

Tổng chữ số nhỏ nhất sau khi thêm số là 1