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$$$.