หาผลรวมหลักตัวเลขน้อยที่สุดหลังจากบวกจำนวน d ใน C++

คำอธิบายปัญหา

ในปัญหานี้ เราได้รับตัวเลขสองจำนวนคือ n และ d ภารกิจของเราคือการหา ผลรวมหลักตัวเลข (digit sum) ที่น้อยที่สุด ที่เป็นไปได้หลังจากบวกจำนวน d เข้ากับ n ซ้ำๆ (คือ บวก k × d โดยที่ k เป็นจำนวนเต็มบวก)

ตัวอย่าง

Input: n = 5230, d = 54

Output: 1

คำอธิบาย: ตัวเลขจะกลายเป็น 5230 + (2 × 54) = 5338 ซึ่งผลรวมหลักตัวเลขคือ 5+3+3+8 = 19 → 1+9 = 10 → 1+0 = 1

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

วิธีการที่ง่ายคือการตรวจสอบทุกคูณของ d ตั้งแต่ 1 ถึง 8 เท่านั้น เนื่องจากที่คูณที่ 9 ผลรวมหลักตัวเลขจะซ้ำรูปแบบเดิม (อาศัยหลัก modulo 9)

หลักการคือ: (n + d × (9k + l)) mod 9 เทียบเท่ากับ (n + d × l) mod 9 ดังนั้นเราตรวจสอบแค่ l = 1 ถึง 8 และหาค่าต่ำสุด

การเพิ่มประสิทธิภาพ: ผลรวมหลักตัวเลขจะไม่มีค่าน้อยกว่า 1 ดังนั้นถ้าพบค่า 1 ให้คืนค่าทันที

โค้ดตัวอย่าง C++

#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 << "The minimum possible digit sum after adding the number is " << findMinDigitSum(n, d);
    return 0;
}

ผลลัพธ์

The minimum possible digit sum after adding the number is 1