smallest-divisible-digit-product-ii.cpp

// Time:  O(n + logt)
// Space: O(1)

// freq table, greedy, prefix sum, number theory
class Solution {
public:
    string smallestNumber(string num, long long t) {
        static const vector<vector<tuple<int, int, int, int>>> LOOKUP = {
            {{0, 0, 0, 0}, {0, 1, 0, 0}},
            {{1, 0, 0, 0}, {0, 0, 0, 1}},
            {{0, 0, 1, 0}, {1, 0, 0, 1}}
        };

        const auto& count = [](int64_t x) {
            vector<int> cnt(10);
            for (int i = 2; i <= 9; ++i) {
                while (x % i == 0) {
                    x /= i;
                    ++cnt[i];
                }
                if (x == 1) {
                    return cnt;
                }
            }
            return vector<int>();
        };
    
        const auto& update = [](auto& total, auto cnt, int d) {
            for (int i = 0; i < size(cnt); ++i) {
                total[i] += d * cnt[i];
            }
        };

        const auto& diff = [](const auto& expect, const auto&total) {
            vector<int> result(10);
            for (int i = 0; i < size(expect); ++i) {
                result[i] = max(expect[i] - total[i], 0);
            }
            return result;
        };

        const auto& min_factors = [](const auto& cnt) {
            const int cnt8 = cnt[2] / 3, r2 = cnt[2] % 3;
            const int cnt9 = cnt[3] / 2, r3 = cnt[3] % 2;
            const auto& [cnt2, cnt3, cnt4, cnt6] = LOOKUP[r2][r3];
            return vector<int>{cnt2, cnt3, cnt4, cnt[5], cnt6, cnt[7], cnt8, cnt9};
        };
        
        const auto& format = [](const auto& cnt, int l) {
            string result(l, '1');
            int i = l - accumulate(cbegin(cnt), cend(cnt), 0);
            for (int x = 2; x <= 9; ++x) {
                for (int _ = 0; _ < cnt[x - 2]; ++_) {
                    result[i++] = '0' + x;
                }
            }
            return result;
        };

        const auto& expect = count(t);
        if (empty(expect)) {
            return "-1";
        }
        int i = 0;
        for (; i < size(num); ++i) {
            if (num[i] == '0') {
                break;
            }
        }
        for (; i < size(num); ++i) {
            num[i] = '1';
        }
        vector<int> total(10);
        for (const auto& x : num) {
            update(total, count(x - '0'), +1);
        }
        const auto& d = diff(expect, total);
        if (all_of(cbegin(d), cend(d), [](const auto& x) {
            return x == 0;
        })) {
            return num;
        }
        for (int i = size(num) - 1; i >= 0; --i) {
            update(total, count(num[i] - '0'), -1);
            for (int x = (num[i] - '0') + 1; x <= 9; ++x) {
                update(total, count(x), +1);
                const auto& tmp = min_factors(diff(expect, total));
                update(total, count(x), -1);
                if (accumulate(cbegin(tmp), cend(tmp), 0) > size(num) - 1 - i) {
                    continue;
                }
                num[i] = '0' + x;
                return num.substr(0, i + 1) + format(tmp, size(num) - 1 - i);
            }
        }
        const auto& result = min_factors(diff(expect, total));
        return format(result, max(static_cast<int>(size(num)) + 1, accumulate(cbegin(result), cend(result), 0)));
    }
};

// Time:  O(nlogt)
// Space: O(logt)
// freq table, greedy, prefix sum, number theory
class Solution2 {
public:
    string smallestNumber(string num, long long t) {
        const auto& find_candidates = [](int64_t t, int l) {  // Time: O(logt)
            vector<int> candidates;
            for (int x = 9; x >= 2; --x) {
                while (t % x == 0) {
                    t /= x;
                    candidates.emplace_back(x);
                    if (size(candidates) > l) {
                        return vector<int>();
                    }
                }
                if (t == 1) {
                    reverse(begin(candidates), end(candidates));
                    return candidates;
                }
            }
            return vector<int>();
        };

        const auto& format = [](const auto& candidates, int l) {
            string result(l, '1');
            int i = size(result) - size(candidates);
            for (const auto& x: candidates) {
                result[i++] = '0' + x;
            }
            return result;
        };
    
        const auto& candidates = find_candidates(t, numeric_limits<int>::max());
        if (t != 1 && empty(candidates)) {
            return "-1";
        }
        int i = 0;
        for (; i < size(num); ++i) {
            if (num[i] == '0') {
                break;
            }
        }
        for (; i < size(num); ++i) {
            num[i] = '1';
        }
        vector<int64_t> prefix(size(num) + 1, 1);
        for (int i = 0; i + 1 < size(prefix); ++i) {
            prefix[i + 1] = (prefix[i] * (num[i] - '0')) % t;
        }
        if (prefix.back() == 0) {
            return num;
        }
        for (int i = size(num) - 1; i >= 0; --i) {
            const int64_t target = t / gcd(t, prefix[i]);
            for (int x = (num[i] - '0') + 1; x <= 9; ++x) {
                const int64_t new_target = target / gcd(target, x);
                const int l = size(num) - 1 - i;
                const auto& tmp = find_candidates(new_target, l);
                if (new_target != 1 && empty(tmp)) {
                    continue;
                }
                num[i] = '0' + x;
                return num.substr(0, i + 1) + format(tmp, l);
            }
        }
        return format(candidates, max(size(num) + 1, size(candidates)));
    }
};