ตัวเลขสูงสุดที่มีผลคูณแฟกทอเรียลของหลักเท่ากันใน C++

ภาพรวมปัญหา

หาตัวเลขสูงสุด (ไม่มีศูนย์นำหน้าหรือศูนย์ท้าย และไม่มีเลข 1) ที่ผลคูณของแฟกทอเรียลของหลักต่างๆ เท่ากับผลคูณแฟกทอเรียลของหลักของตัวเลข N ที่กำหนด

ตัวอย่าง

Input: N = 4912
Output: 73332222
Explanation: 4! * 9! * 1! * 2! = 7! * 3! * 3! * 3! * 2! * 2! * 2! * 2! = 17,418,240

Input: N = 340
Output: 3322

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

• แยกตัวเลขแต่ละหลักเป็นผลคูณของแฟกทอเรียลของจำนวนเฉพาะ
• 4! = 2! × 2! × 3!
• 6! = 5! × 3!
• 8! = 7! × 2! × 2! × 2!
• 9! = 7! × 3! × 3! × 2!
• นับความถี่ของแต่ละตัวเลข (2, 3, 5, 7)
• จัดเรียงตัวเลขจากมากไปน้อยเพื่อให้ได้ตัวเลขสูงสุด

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

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

string MaxNum(string str) {
    int total_digits = str.length();
    int Frq[15] = { 0 };
    
    for (int i = 0; i < total_digits; i++) {
        if (str[i] == '1' || str[i] == '2' || str[i] == '3' || str[i] == '5' || str[i] == '7') {
            Frq[str[i] - 48] += 1;
        }
        if (str[i] == '4') { Frq[2] += 2; Frq[3]++; }
        if (str[i] == '6') { Frq[5]++; Frq[3]++; }
        if (str[i] == '8') { Frq[7]++; Frq[2] += 3; }
        if (str[i] == '9') { Frq[7]++; Frq[3] += 2; Frq[2]++; }
    }
    
    string ans = "";
    if (Frq[1] == total_digits || Frq[0] == total_digits || (Frq[0] + Frq[1]) == total_digits) {
        return str;
    } else {
        for (int i = 9; i >= 2; i--) {
            int C = Frq[i];
            while (C--) ans += (char)(i + 48);
        }
        return ans;
    }
}

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

ผลลัพธ์

3322