Minimum Factorization – หาตัวเลขน้อยที่สุดที่คูณหลักได้เท่ากับเป้าหมายใน C++

ปัญหา: Minimum Factorization

กำหนดจำนวนเต็มบวก x หา จำนวนเต็มบวกที่น้อยที่สุด b ที่ ผลคูณของหลักต่างๆ ของ b เท่ากับ x
ไม่มีคำตอบ → คืน 0

ตัวอย่าง

x = 48 → Output: 68 (6 × 8 = 48, และ 68 < 86)

แนวทางแก้ปัญหา: Greedy – แยกตัวประกอบจาก 9 ลงมา 2

เหตุผล

• ต้องการตัวเลข น้อยที่สุด → หลักสิบต้องน้อยที่สุด → ใช้ตัวประกอบ ใหญ่ที่สุด ก่อน (9,8,7...)
• ตัวประกอบใหญ่ = หลักน้อยลง = ตัวเลขสั้นกว่า = ค่าน้อยกว่า
• เช่น 48 = 6×8 (2 หลัก) ดีกว่า 2×2×2×2×3 (5 หลัก)

ขั้นตอน

1. ถ้า x < 2 → คืน x (0→0, 1→1)
2. ลูป i = 9..2:
   • while x % i == 0: เก็บ i, x /= i
3. ถ้า x > 1 → ไม่สามารถแยกได้หมด → คืน 0
4. ตัวประกอบที่เก็บได้ → เรียงจากน้อยไปมาก (เพราะเก็บจาก 9 ลงมา) → รวมเป็นตัวเลข

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int smallestFactorization(int a) {
        if (a < 2) return a;

        long long result = 0;
        long long multiplier = 1;

        for (int i = 9; i >= 2; i--) {
            while (a % i == 0) {
                result = i * multiplier + result; // prepend digit
                multiplier *= 10;
                a /= i;
            }
        }

        return (a < 2 && result < INT_MAX) ? result : 0;
    }
};

int main() {
    Solution ob;
    cout << ob.smallestFactorization(48);  // 68
    cout << ob.smallestFactorization(15);  // 35 (3×5)
    cout << ob.smallestFactorization(13);  // 0 (prime > 9)
    return 0;
}

ตัวอย่างการทำงาน (48)

i=9: 48%9≠0
i=8: 48%8=0 → result=8, a=6
i=7: 6%7≠0
i=6: 6%6=0 → result=68, a=1
i=5..2: a=1 stop
Result: 68 ✓

ความซับซ้อน

• เวลา: O(log x) – ลูป 9..2, แต่ละ while ลด x ลงอย่างน้อย 2 เท่า
• พื้นที่: O(1)

ข้อสังเกต

• LeetCode 625 (Minimum Factorization)
• Greedy ถูกต้องเพราะ: ตัวเลขน้อยที่สุด ⇔ จำนวนหลักน้อยที่สุด ⇔ ใช้ตัวประกอบใหญ่ที่สุด
• กรณี x เป็นเฉพาะ > 9 → คืน 0 (เช่น 11, 13, 17...)
• ใช้ long long สำหรับ result ป้องกัน overflow (INT_MAX = 2,147,483,647)