Phân tích nhân tử tối thiểu trong C++

Giới thiệu

Cho số nguyên dương x. Tìm số nguyên dương b nhỏ nhất sao cho tích các chữ số của b bằng x. Nếu không tồn tại trả về 0.

Thuật toán: Tham lam từ chữ số 9 xuống 2

Để số kết quả nhỏ nhất (về giá trị số học), ta muốn ít chữ số nhất và chữ số nhỏ ở hàng cao. Do đó, thử chia x cho các chữ số từ 9 xuống 2. Mỗi lần chia hết, thêm chữ số đó vào kết quả (đẩy lên hàng cao hơn bằng cách nhân 10).

Cài đặt C++

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

class Solution {
public:
    int smallestFactorization(int a) {
        if (a < 2) return a; // 0 hoặc 1
        long long res = 0, mul = 1;
        for (int d = 9; d >= 2; d--) {
            while (a % d == 0) {
                res = d * mul + res; // thêm chữ số d ở hàng cao hơn
                mul *= 10;
                a /= d;
            }
        }
        return (a < 2 && res < INT_MAX) ? (int)res : 0;
    }
};

int main() {
    Solution ob;
    cout << ob.smallestFactorization(48); // Output: 68 (6*8=48)
    // 48 = 6*8 -> số 68 nhỏ hơn 86
    return 0;
}

Giải thích ví dụ

x = 48.

• Thử 9: không chia hết.
• Thử 8: 48/8=6 → thêm 8, res=8, mul=10.
• Thử 7..6: 6/6=1 → thêm 6, res=6*10+8=68.
• a=1 < 2 → trả 68.

Độ phức tạp

• Thời gian: O(log x) – số vòng lặp chia.
• Không gian: O(1).

LeetCode 625 "Minimum Factorization".