หาตัวเลขมากที่สุดที่มี N หลักและผลรวมหลักเท่ากับ Sum ใน C++

ในปัญหานี้ เราได้รับ N (จำนวนหลัก) และ Sum (ผลรวมหลัก) งานคือหาตัวเลขมากที่สุดที่ตรงเงื่อนไข

ตัวอย่าง

Input: N = 3, Sum = 15 Output: 960

วิธีที่ 1: Brute Force (ช้า)

วนจากตัวเลข N หลักมากที่สุดลงมา หาตัวแรกที่ผลรวมหลัก = Sum

วิธีที่ 2: Greedy Approach (แนะนำ) O(N)

เติมหลักจาก MSB (most significant bit) ไป LSB:

• ถ้า Sum >= 9 → ใส่ 9, ลบ Sum 9
• ถ้า Sum < 9 → ใส่ Sum, ตั้ง Sum = 0
• ทำซ้ำ N ครั้ง

ตัวอย่างโค้ด (Greedy)

#include <iostream>
using namespace std;

int findLargestNumWithSum(int N, int sum) {
    if (sum == 0) return (N == 1) ? 0 : -1;
    if (sum > 9 * N) return -1; // impossible
    
    int num = 0;
    for (int i = 0; i < N; i++) {
        if (sum >= 9) { num = num * 10 + 9; sum -= 9; }
        else { num = num * 10 + sum; sum = 0; }
    }
    return num;
}

int main() {
    cout << findLargestNumWithSum(3, 25); // 997
    return 0;
}

ผลลัพธ์

997

(9+9+7=25, 3 หลัก, มากที่สุด)