3348. Smallest Divisible Digit Product II

#include <stdlib.h>   // malloc / 動態配置記憶體
#include <string.h>   // strlen, memcpy / 字串長度與複製

// 回傳數字 d(1..9) 的質因數 2,3,5,7 指數 / prime exponents (2,3,5,7) of digit d
static void digExp(int d, int *a2, int *a3, int *a5, int *a7) {
    int e2 = 0, e3 = 0, e5 = 0, e7 = 0;      // 預設全為 0 / default all zero
    switch (d) {                             // 依數字查表 / lookup by digit
        case 2: e2 = 1; break;               // 2 = 2^1
        case 3: e3 = 1; break;               // 3 = 3^1
        case 4: e2 = 2; break;               // 4 = 2^2
        case 5: e5 = 1; break;               // 5 = 5^1
        case 6: e2 = 1; e3 = 1; break;       // 6 = 2·3
        case 7: e7 = 1; break;               // 7 = 7^1
        case 8: e2 = 3; break;               // 8 = 2^3
        case 9: e3 = 2; break;               // 9 = 3^2
        default: break;                      // 1(或0) 不貢獻 / 1 (or 0) contributes nothing
    }
    *a2 = e2; *a3 = e3; *a5 = e5; *a7 = e7;  // 用指標把結果寫回呼叫端 / write back via pointers
}

// 覆蓋剩餘指數所需的「最少位數」/ minimum digit count to cover the residual exponents
static int minDigits(int r2, int r3, int r5, int r7) {
    if (r2 < 0) r2 = 0; if (r3 < 0) r3 = 0;  // 負數代表已滿足，視為 0 / clamp negatives to 0
    if (r5 < 0) r5 = 0; if (r7 < 0) r7 = 0;
    int e8 = r2 / 3, rem2 = r2 % 3;          // 每個 8 吃掉三個 2 / each 8 absorbs three 2's
    int n9 = r3 / 2, rem3 = r3 % 2;          // 每個 9 吃掉兩個 3 / each 9 absorbs two 3's
    int lc;                                  // 零頭需要的位數 / digits for the leftovers
    if (rem2 == 0 && rem3 == 0) lc = 0;      // 無零頭 / nothing left
    else if (rem2 == 2 && rem3 == 1) lc = 2; // 2^2·3 → 需兩位(如 2,6) / needs two digits
    else lc = 1;                             // 其餘情形一位即可 / one digit otherwise
    return e8 + n9 + lc + r5 + r7;           // 5 與 7 各只能靠 '5','7' / only '5','7' give 5,7
}

// 把「長度剛好 k、覆蓋剩餘指數的最小字串」寫進 dest / write smallest length-k covering string
static void fillSuffix(char *dest, int k, int r2, int r3, int r5, int r7) {
    if (r2 < 0) r2 = 0; if (r3 < 0) r3 = 0;  // 同樣把負值歸零 / clamp negatives
    if (r5 < 0) r5 = 0; if (r7 < 0) r7 = 0;
    int c8 = r2 / 3, rem2 = r2 % 3;          // 8 的個數與 2 的零頭 / count of 8's, leftover 2's
    int c9 = r3 / 2, rem3 = r3 % 2;          // 9 的個數與 3 的零頭 / count of 9's, leftover 3's
    int c2 = 0, c3 = 0, c4 = 0, c6 = 0;      // 零頭湊出的小數字 / small digits from leftovers
    if (rem2 == 1 && rem3 == 0) c2 = 1;      // 剩一個 2 → '2'
    else if (rem2 == 2 && rem3 == 0) c4 = 1; // 剩兩個 2 → '4'(=2^2 只花一位) / one digit
    else if (rem2 == 0 && rem3 == 1) c3 = 1; // 剩一個 3 → '3'
    else if (rem2 == 1 && rem3 == 1) c6 = 1; // 剩一個2一個3 → '6'(併成一位) / merge into 6
    else if (rem2 == 2 && rem3 == 1) { c2 = 1; c6 = 1; } // 2^2·3 → "26" 最小 / smallest
    int c5 = r5, c7 = r7;                     // 5 和 7 直接放 / place 5's and 7's directly
    int m = c2 + c3 + c4 + c5 + c6 + c7 + c8 + c9;  // 有效數字總數 / count of non-1 digits
    int idx = 0;                              // 目前寫到的位置 / current write index
    for (int i = 0; i < k - m; i++) dest[idx++] = '1'; // 多的位補 '1' 放最前(最小) / pad 1's
    for (int i = 0; i < c2; i++) dest[idx++] = '2';    // 之後由小到大輸出 / then ascending
    for (int i = 0; i < c3; i++) dest[idx++] = '3';
    for (int i = 0; i < c4; i++) dest[idx++] = '4';
    for (int i = 0; i < c5; i++) dest[idx++] = '5';
    for (int i = 0; i < c6; i++) dest[idx++] = '6';
    for (int i = 0; i < c7; i++) dest[idx++] = '7';
    for (int i = 0; i < c8; i++) dest[idx++] = '8';
    for (int i = 0; i < c9; i++) dest[idx++] = '9';     // idx 最終等於 k / idx ends at k
}

/* 演算法 / Algorithm:
   1) 把 t 除盡 2,3,5,7；若有殘餘>1 則無解回 "-1"。
   2) num 本身無零且乘積合格就直接回傳。
   3) 否則從右往左找「增大位置」湊出同長度的最小合格數；找不到就用長度 L+1。*/
char* smallestNumber(char* num, long long t) {
    int L = strlen(num);                     // num 的位數 / number of digits
    long long tt = t;                        // 複製 t 來做分解 / copy for factoring
    int e2 = 0, e3 = 0, e5 = 0, e7 = 0;      // 需要的質因數指數 / required exponents
    while (tt % 2 == 0) { tt /= 2; e2++; }   // 除盡 2 / strip factors of 2
    while (tt % 3 == 0) { tt /= 3; e3++; }   // 除盡 3
    while (tt % 5 == 0) { tt /= 5; e5++; }   // 除盡 5
    while (tt % 7 == 0) { tt /= 7; e7++; }   // 除盡 7
    if (tt != 1) {                           // 還有其他質因數 → 不可能整除 / impossible
        char *r = malloc(3); strcpy(r, "-1"); return r;  // 配置並回傳 "-1"
    }

    int z = L;                               // 第一個 '0' 的位置(沒有則 = L) / first zero index
    for (int i = 0; i < L; i++) if (num[i] == '0') { z = i; break; }

    long long T2 = 0, T3 = 0, T5 = 0, T7 = 0;    // 整個 num 的指數總和 / totals over all digits
    for (int i = 0; i < L; i++) {
        int a2, a3, a5, a7; digExp(num[i] - '0', &a2, &a3, &a5, &a7); // num[i]-'0' 由字元轉數字
        T2 += a2; T3 += a3; T5 += a5; T7 += a7;
    }
    if (z == L && T2 >= e2 && T3 >= e3 && T5 >= e5 && T7 >= e7) {  // num 無零且已合格 / valid
        char *r = malloc(L + 1); memcpy(r, num, L); r[L] = ''; return r; // 複製一份回傳
    }

    int pmax = (L - 1 < z) ? (L - 1) : z;    // 增大位置最多到第一個 0 / cannot keep a zero
    long long p2 = 0, p3 = 0, p5 = 0, p7 = 0;    // 前綴 num[0..p-1] 的指數 / prefix exponents
    for (int i = 0; i < pmax; i++) {         // 先算 pmax 的前綴指數 / init prefix at p = pmax
        int a2, a3, a5, a7; digExp(num[i] - '0', &a2, &a3, &a5, &a7);
        p2 += a2; p3 += a3; p5 += a5; p7 += a7;
    }

    int bestP = -1, bestD = -1;              // 最佳增大位置與數字 / chosen position & digit
    int BR2 = 0, BR3 = 0, BR5 = 0, BR7 = 0;  // 對應的剩餘指數 / residual exponents for suffix
    for (int p = pmax; p >= 0; p--) {        // 從右往左掃(前綴越長越好) / scan right-to-left
        int dp = num[p] - '0';               // 目前這一位的值 / current digit value
        for (int d = dp + 1; d <= 9; d++) {  // 試最小的、比它大的數字 / smallest larger digit
            int a2, a3, a5, a7; digExp(d, &a2, &a3, &a5, &a7);      // d 的指數 / exps of d
            long long r2 = e2 - p2 - a2, r3 = e3 - p3 - a3;         // 扣掉前綴與 d / subtract
            long long r5 = e5 - p5 - a5, r7 = e7 - p7 - a7;
            int R2 = r2 < 0 ? 0 : (int)r2, R3 = r3 < 0 ? 0 : (int)r3; // 負→0 / clamp
            int R5 = r5 < 0 ? 0 : (int)r5, R7 = r7 < 0 ? 0 : (int)r7;
            int slots = L - 1 - p;           // 後面剩幾個空位 / remaining empty slots
            if (minDigits(R2, R3, R5, R7) <= slots) {   // 塞得下 → 可行 / feasible
                bestP = p; bestD = d;        // 記住答案 / record
                BR2 = R2; BR3 = R3; BR5 = R5; BR7 = R7;
                break;                       // 取最小的 d / take smallest feasible d
            }
        }
        if (bestP != -1) break;              // 取最右(最大)的 p / take right-most feasible p
        if (p - 1 >= 0) {                    // 前綴縮短一位:扣掉 num[p-1] / shrink prefix by 1
            int a2, a3, a5, a7; digExp(num[p - 1] - '0', &a2, &a3, &a5, &a7);
            p2 -= a2; p3 -= a3; p5 -= a5; p7 -= a7;
        }
    }

    if (bestP != -1) {                       // 找到同長度答案 / same-length answer found
        char *r = malloc(L + 1);
        memcpy(r, num, bestP);               // 保留前綴 / keep prefix num[0..bestP-1]
        r[bestP] = (char)('0' + bestD);      // 放入增大後的數字 / place increased digit
        fillSuffix(r + bestP + 1, L - 1 - bestP, BR2, BR3, BR5, BR7); // 填最小後綴 / fill suffix
        r[L] = '';                         // 收尾 / null-terminate
        return r;
    }

    int m = minDigits(e2, e3, e5, e7);       // 湊出 t 的最少位數 / min digits to realise t
    int outLen = (L + 1 > m) ? (L + 1) : m;  // 至少比 num 長一位 / at least L+1 (or m)
    char *r = malloc(outLen + 1);
    fillSuffix(r, outLen, e2, e3, e5, e7);   // 前補 1、後放最小數字 / pad 1's then digits
    r[outLen] = '';
    return r;
}

#include <string>
#include <array>
#include <algorithm>
using namespace std;

/* 演算法 / Algorithm:
   1) 分解 t 為 2,3,5,7 的指數;有其他質因數則回 "-1"。
   2) num 本身無零且乘積合格就回傳。
   3) 否則右往左找增大位置湊同長度最小合格數;失敗則用長度 L+1。*/
class Solution {
public:
    // 回傳數字 d(1..9) 的 (2,3,5,7) 指數;用 std::array 一次回傳四個值
    // return the (2,3,5,7) exponents of digit d; std::array carries all four at once
    static array<int, 4> digExp(int d) {
        switch (d) {                             // 依數字查表 / lookup by digit
            case 2: return {1, 0, 0, 0};         // 2 = 2^1
            case 3: return {0, 1, 0, 0};         // 3 = 3^1
            case 4: return {2, 0, 0, 0};         // 4 = 2^2
            case 5: return {0, 0, 1, 0};         // 5 = 5^1
            case 6: return {1, 1, 0, 0};         // 6 = 2·3
            case 7: return {0, 0, 0, 1};         // 7 = 7^1
            case 8: return {3, 0, 0, 0};         // 8 = 2^3
            case 9: return {0, 2, 0, 0};         // 9 = 3^2
            default: return {0, 0, 0, 0};        // 1(或0) 無貢獻 / no contribution
        }
    }

    // 覆蓋剩餘指數所需的最少位數 / minimum digit count to cover residual exponents
    static int minDigits(int r2, int r3, int r5, int r7) {
        int e8 = r2 / 3, rem2 = r2 % 3;          // 每個 8 = 三個 2 / each 8 covers three 2's
        int n9 = r3 / 2, rem3 = r3 % 2;          // 每個 9 = 兩個 3 / each 9 covers two 3's
        int lc;                                  // 零頭需要的位數 / digits for leftovers
        if (rem2 == 0 && rem3 == 0) lc = 0;
        else if (rem2 == 2 && rem3 == 1) lc = 2; // 2^2·3 需兩位 / needs two digits
        else lc = 1;
        return e8 + n9 + lc + r5 + r7;           // 5,7 只能各佔一位 / only 5/7 give those primes
    }

    // 回傳「長度剛好 k、覆蓋剩餘指數的最小字串」/ smallest length-k covering string
    static string fillSuffix(int k, int r2, int r3, int r5, int r7) {
        int c8 = r2 / 3, rem2 = r2 % 3;          // 8 的數量與 2 的零頭 / 8's and leftover 2's
        int c9 = r3 / 2, rem3 = r3 % 2;          // 9 的數量與 3 的零頭 / 9's and leftover 3's
        int c2 = 0, c3 = 0, c4 = 0, c6 = 0;      // 零頭湊出的數字 / digits from leftovers
        if (rem2 == 1 && rem3 == 0) c2 = 1;      // '2'
        else if (rem2 == 2 && rem3 == 0) c4 = 1; // '4' 一位覆蓋 2^2 / one digit for 2^2
        else if (rem2 == 0 && rem3 == 1) c3 = 1; // '3'
        else if (rem2 == 1 && rem3 == 1) c6 = 1; // '6' 併掉一個2一個3 / merge 2 and 3
        else if (rem2 == 2 && rem3 == 1) { c2 = 1; c6 = 1; } // "26" 最小 / smallest for 2^2·3
        int m = c2 + c3 + c4 + r5 + c6 + r7 + c8 + c9;  // 有效數字數 / count of non-1 digits
        string s;                                // 用 std::string 累積結果 / build the result
        s.reserve(k);                            // 預留空間避免多次配置 / avoid reallocations
        s.append(k - m, '1');                    // append(n,ch): 補 n 個 '1' 在最前 / pad 1's
        s.append(c2, '2'); s.append(c3, '3'); s.append(c4, '4');  // 之後由小到大 / ascending
        s.append(r5, '5'); s.append(c6, '6'); s.append(r7, '7');
        s.append(c8, '8'); s.append(c9, '9');
        return s;                                // 長度剛好 k / length is exactly k
    }

    string smallestNumber(string num, long long t) {
        int L = num.size();                      // 位數 / number of digits
        long long tt = t;                        // 複製來分解 / copy for factoring
        int e2 = 0, e3 = 0, e5 = 0, e7 = 0;      // 需要的指數 / required exponents
        while (tt % 2 == 0) { tt /= 2; e2++; }   // 除盡各質因數 / strip 2,3,5,7
        while (tt % 3 == 0) { tt /= 3; e3++; }
        while (tt % 5 == 0) { tt /= 5; e5++; }
        while (tt % 7 == 0) { tt /= 7; e7++; }
        if (tt != 1) return "-1";                // 殘餘>1 → 無解 / impossible

        int z = L;                               // 第一個 '0' 位置 / index of first zero
        for (int i = 0; i < L; i++) if (num[i] == '0') { z = i; break; }

        long long T2 = 0, T3 = 0, T5 = 0, T7 = 0;    // 整串指數總和 / totals over whole num
        for (char c : num) {                     // range-for: 逐字元走訪 / iterate each char
            auto e = digExp(c - '0');            // auto 讓編譯器推導型別 / deduced array type
            T2 += e[0]; T3 += e[1]; T5 += e[2]; T7 += e[3];
        }
        if (z == L && T2 >= e2 && T3 >= e3 && T5 >= e5 && T7 >= e7)
            return num;                          // num 無零且合格 / already valid

        int pmax = min(L - 1, z);                // 增大位置上限(不可保留 0) / cap at first zero
        long long p2 = 0, p3 = 0, p5 = 0, p7 = 0;    // 前綴指數 / prefix exponents
        for (int i = 0; i < pmax; i++) {         // 初始化為 p=pmax 的前綴 / prefix at pmax
            auto e = digExp(num[i] - '0');
            p2 += e[0]; p3 += e[1]; p5 += e[2]; p7 += e[3];
        }

        int bestP = -1, bestD = -1;              // 最佳位置與數字 / chosen position & digit
        int BR2 = 0, BR3 = 0, BR5 = 0, BR7 = 0;  // 對應剩餘指數 / residual for suffix
        for (int p = pmax; p >= 0; p--) {        // 右往左(前綴越長越小) / right-to-left
            int dp = num[p] - '0';               // 當前位的值 / current digit value
            for (int d = dp + 1; d <= 9; d++) {  // 最小的更大數字 / smallest larger digit
                auto e = digExp(d);              // d 的指數 / exponents of d
                long long r2 = e2 - p2 - e[0], r3 = e3 - p3 - e[1]; // 扣前綴與 d / subtract
                long long r5 = e5 - p5 - e[2], r7 = e7 - p7 - e[3];
                int R2 = max(0LL, r2), R3 = max(0LL, r3);   // 負→0 / clamp to 0
                int R5 = max(0LL, r5), R7 = max(0LL, r7);
                if (minDigits(R2, R3, R5, R7) <= L - 1 - p) {   // 塞得下 / feasible
                    bestP = p; bestD = d;        // 記錄(最小 d) / record smallest d
                    BR2 = R2; BR3 = R3; BR5 = R5; BR7 = R7;
                    break;
                }
            }
            if (bestP != -1) break;              // 取最右可行 p / take right-most p
            if (p - 1 >= 0) {                    // 前綴縮一位 / shrink prefix by one digit
                auto e = digExp(num[p - 1] - '0');
                p2 -= e[0]; p3 -= e[1]; p5 -= e[2]; p7 -= e[3];
            }
        }

        if (bestP != -1) {                       // 同長度答案 / same-length answer
            string ans = num.substr(0, bestP);   // 保留前綴 / keep prefix
            ans += char('0' + bestD);            // 加上增大後的數字 / append increased digit
            ans += fillSuffix(L - 1 - bestP, BR2, BR3, BR5, BR7); // 加最小後綴 / minimal suffix
            return ans;
        }

        int m = minDigits(e2, e3, e5, e7);       // 湊出 t 的最少位數 / min digits for t
        int outLen = max(L + 1, m);              // 必須比 num 長 / must be longer than num
        return fillSuffix(outLen, e2, e3, e5, e7); // 前補 1、後放最小數字 / pad then digits
    }
};