Finding the k-th m-Number: ACES Brainstorming Challenge Solution Day 1

A number is called an m-number if the product of its digits equals a given positive integer m. For example, when m = 24, the series of m-numbers starts as follows: 38, 46, 64, 83, 138, 146, 164, 183, 226, and so on. You are given a positive integer m, and you need to find the k-th smallest m-number, where the m-numbers are arranged in ascending order. Find the k-th m-number in the sorted sequence of m-numbers for the given value of m if: m = 5040 k = 1000000000

Answer: 111121111315213227111

Explanation:

#include <iostream>
#include <vector>
#include <map>
#include <array>
#include <algorithm>
#include <cassert>

using namespace std;

vector<int> primes = {2, 3, 5, 7};

// Factorizes a number into counts of powers of the first 4 primes.
array<int, 4> factor(int m) {
    array<int, 4> f = {0, 0, 0, 0};
    if (m <= 1) return f;
    for (int i = 0; i < primes.size(); i++) {
        while (m % primes[i] == 0) {
            m /= primes[i];
            f[i]++;
        }
    }
    return m == 1 ? f : array<int, 4>{-1, -1, -1, -1};
}

vector<array<int, 4>> factors(10);
map<int64_t, int64_t> dp;
vector<int> digits(100000);

int64_t encodeState(const array<int, 4>& f, int nd) {
    return f[0] + (f[1] << 5) + (f[2] << 10) + (f[3] << 15) + (static_cast<int64_t>(nd) << 20);
}

int64_t count(array<int, 4>& f, int nd, int64_t p = -1) {
    int64_t e = encodeState(f, nd);
    if (nd == 0) return e == 0 ? 1 : 0;
    if (p == -1 && dp.count(e)) return dp[e];
    int64_t cnt = 0;
    for (int d = 1; d <= 9; d++) {
        digits[nd - 1] = d;
        auto df = factors[d];
        bool valid = true;
        for (int i = 0; i < 4; i++) {
            f[i] -= df[i];
            if (f[i] < 0) valid = false;
        }
        if (valid) {
            int64_t nc = count(f, nd - 1);
            if (p >= 0 && cnt + nc > p) return count(f, nd - 1, p - cnt);
            cnt += nc;
        }
        for (int i = 0; i < 4; i++) f[i] += df[i];
    }
    if (p == -1) dp[e] = cnt;
    return cnt;
}

int main() {
    int m, k;
    cin >> m >> k;

    // Precompute factors for digits 0-9
    for (int i = 0; i <= 9; i++) factors[i] = factor(i);

    auto f = factor(m);
    if (f[0] == -1) {
        cout << -1 << endl;
        return 0;
    }

    dp.clear();
    int nd = 1;
    int64_t num = 1;
    while (count(f, nd) <= k - num) num += count(f, nd++);
    assert(count(f, nd, k - num) == 1);

    string result;
    for (int i = nd - 1; i >= 0; i--) result += to_string(digits[i]);
    cout << result << endl;

    return 0;
}

This program computes the (k)-th lexicographical representation of a number (m) as a product of digits (from 1 to 9). The output is the smallest number (lexicographically) whose digits' product equals (m).

Key Concepts and Workflow

1. Prime Factorization:

   • Any number (m) can be decomposed into its prime factors. This code limits prime factorization to the first four primes: (2, 3, 5, 7). Any number that requires other primes or cannot be decomposed by these is invalid for this problem.

   array<int, 4> factor(int m)
   

   • This function computes the count of each prime factor for (m). If (m) contains primes other than (2, 3, 5, 7), it returns ([-1, -1, -1, -1]).

2. State Representation:

   • The program uses a dynamic programming (DP) approach to compute the number of valid representations of (m). Each state is encoded as:

     int64_t encodeState(const array<int, 4>& f, int nd)
     

     • (f[i]): The remaining count of each prime factor (i).
     • (nd): The number of digits remaining to construct the product.
     • The state encoding helps store results for previously computed states to avoid redundant computations.

3. Counting Valid Representations:

   • The function count recursively counts how many representations of (m) can be formed using up to nd digits.
   • It iterates over digits (1) through (9), subtracting their contributions (precomputed in factors) from the factorization array f. If valid, it recurses for the next digit.

4. Finding the (k)-th Representation:

   • The program iteratively increases the number of digits (nd) and checks if the (k)-th representation lies within the range of cumulative counts for that digit length.
   • Once the correct digit length is found, the program backtracks through the recursive calls to construct the (k)-th representation.

5. Precomputations:

   • Factorizations of digits (0-9) are precomputed for efficiency:

     for (int i = 0; i <= 9; i++) factors[i] = factor(i);
     

6. Main Workflow:

   • Input (m) and (k).
   • Compute the factorization of (m). If invalid, output (-1).
   • Use DP to count valid representations and find the (k)-th one.
   • Construct the result string from digits recorded during recursion.

---

Output Explanation for Input (m=111121111315213227, k=111)

For this input:

• (m) is factorized using ([2, 3, 5, 7]).
• The program computes lexicographical representations of (m) using digits (1)-(9).
• The (111)-th representation (sorted lexicographically) is constructed and printed as 111121111315213227.

This specific result depends on the factorization of (m) and the recursive traversal through valid states.