Số lớn nhất có tích giai thừa chữ số giống nhau trong C++

Cho số nguyên N (dưới dạng chuỗi). Tìm số lớn nhất (không có số 0 dẫn đầu) sao cho tích giai thừa các chữ số của nó bằng tích giai thừa các chữ số của N.

Ví dụ

Input: N = "4912"
Output: 73332222
Giải thích: 4! * 9! * 1! * 2! = 7! * 3! * 3! * 3! * 2! * 2! * 2! * 2! = 17,418,240

Input: N = "340"
Output: 3322

Ý tưởng thuật toán

Để số kết quả lớn nhất, ta phân tích từng chữ số của N thành tích các giai thừa số nguyên tố (2, 3, 5, 7) vì:

• 4! = 2! * 2! * 3! → thay 4 bằng 3, 2, 2
• 6! = 5! * 3! → thay 6 bằng 5, 3
• 8! = 7! * 2! * 2! * 2! → thay 8 bằng 7, 2, 2, 2
• 9! = 7! * 3! * 3! * 2! → thay 9 bằng 7, 3, 3, 2

Các số nguyên tố 2, 3, 5, 7 giữ nguyên. Số 0 và 1 bỏ qua (vì 0! = 1! = 1).

Sau khi đếm tần suất các chữ số 2,3,5,7, ta ghép chúng theo thứ tự giảm dần (9→2) để tạo số lớn nhất.

Chương trình C++

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

string MaxNum(string str) {
    int freq[10] = {0};
    int n = str.length();
    
    for (char c : str) {
        int d = c - '0';
        if (d == 0 || d == 1) continue; // Bỏ qua
        else if (d == 2 || d == 3 || d == 5 || d == 7) freq[d]++;
        else if (d == 4) { freq[2] += 2; freq[3]++; }
        else if (d == 6) { freq[5]++; freq[3]++; }
        else if (d == 8) { freq[7]++; freq[2] += 3; }
        else if (d == 9) { freq[7]++; freq[3] += 2; freq[2]++; }
    }
    
    // Kiểm tra chỉ có 0 và 1
    bool only01 = true;
    for (char c : str) if (c != '0' && c != '1') { only01 = false; break; }
    if (only01) return str;
    
    string ans = "";
    for (int d = 9; d >= 2; d--)
        while (freq[d]--) ans += char('0' + d);
    return ans;
}

int main() {
    string str = "340";
    cout << MaxNum(str); // Output: 3322
    return 0;
}

Kết quả

3322