I think that when you see a k, you can try to make all numbers with k digits and then calculate the product of each one and the sum of each one. If the product is greater than or equal to the sum, store it in a dictionary, where the dictionary key is the product and the dictionary value is the list of the numbers (maybe in string form to save some space). Then find the minimum key in the dictionary, sort that corresponding list, and return the first element in the list.

Edit: oh wait, the answer is just "0" * k

I'm sure a simple brute force will work.

First, it's clearly obvious that the digits are in ascending order from 1 to 9. So, we just have to think about how many times each digit appears in the string.

The maximum sum of the digits is bounded by $$$9K \leq 900000$$$. In particular, this implies that the number of digit 2 is bounded by $$$\lceil\log_2(9K)\rceil$$$ (since more number of digits would clearly make the product exceed the sum). Similarly, the number of digit 3 is bounded by $$$\lceil\log_3(9K)\rceil$$$, and in general, the number of digit $$$d$$$ is bounded by $$$\lceil\log_d(9K)\rceil$$$.

So, the total number of ways of choosing the digits from 2 to 9 is bounded by $$$\prod_{d = 2}^{9} (\lceil \log_d(9K) \rceil + 1)$$$. If you actually compute this quantity with $$$K = 100000$$$, you'll find out that this is less than $$$2 * 10^8$$$. Of course, this is actually a pretty loose upper bound, and you can likely prune away many, since many of the products would far exceed the sum upper bound $$$9K$$$.

The sum of digits is bounded by 9*k. To make product of digits at least 9*k we need at most ceil(log2(9*k)) digits greater than 1. If we had more than ceil(log2(9*k)) digits greater than 1, then we could turn the least digit greater than 1 into 1, reducing product of digits and making string lexicographically smaller. Therefore having at most ceil(log2(9*k)) digits greater than 1 is optimal. Let's denote ceil(log2(9*k)) as l. Sum of last l digits is bounded by 9*l. Let's maintain dp[i][j], sum of last l digits is i, product of them is at least j, dp[i][j] gives information about whether this state can be achieved and if so, which digit was the last used one. Dimension of dp will be [l*9][k+l*8]. Time complexity is O(klog^2(k)), space complexity is O(klog(k)) .

First, answer for N=6 is 111126

You can't assume 6 non-one digits. For example 8179, lowest product is 8192=2^13, and "1" * 8166 + "2" * 13 has sum 8192, so its tight.

I think easiest way to proceed is for each product P = K, K+1, ... check if its achievable. Brute force is enough, we should expect to hit an answer fairly fast, you can code this then check it finds an answer for every K.

def solve(K):
    for P in range(K, K + 2000):
        expos = [0, 0, 0, 0]

        cur = P
        for i, x in enumerate([2, 3, 5, 7]):
            while cur % x == 0:
                cur //= x
                expos[i] += 1
        if cur != 1:
            continue

        count = [0] * 10
        count[5] = expos[2]
        count[7] = expos[3]

        results = []
        for count[6] in range(1 + min(expos[:2])):
            alpha, beta = expos[:2]
            alpha -= count[6]
            beta -= count[6]
            for count[8] in range(1 + alpha // 3):
                alpha2 = alpha - 3 * count[8]
                for count[4] in range(1 + alpha2 // 2):
                    count[2] = alpha2 - 2 * count[4]
                    for count[9] in range(1 + beta // 2):
                        count[3] = beta - count[9] * 2

                        count[1] = K - sum(count[2:])
                        if count[1] >= 0:
                            total = sum(i * x for i, x in enumerate(count))
                            if total <= P:
                                results.append(count[:])

        if results:
            return "".join(str(i) * x for i, x in enumerate(max(results)))

Auto comment: topic has been updated by Summer_Wind (previous revision, new revision, compare).