PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
There is a fairly well-known greedy algorithm for solving the product of digits problem in base 10. Simply take as many 9’s as possible, then as many 8’s as possible, and so on. For example, to find the smallest number whose product of digits is 1080, begin by taking out a 9 (leaving 120), then take out an 8 (leaving 15), then a 5 (leaving 3), then a 3, so the answer is 3589. Unfortunately this doesn’t carry over to higher bases. Consider the number 22 * 34 * 5 4 in base 19. Using the greedy approach, we’d first extract two 18’s (leaving 54), then four 5’s, for an answer of 5555II. However, a better answer is 4FFFF (four 15’s and one 4). Thus the subproblem of finding the smallest number in a fixed base must be solved with another method.
Additionally, the smallest base for which an answer is possible may not be base with the smallest answer. The smallest counterexample is “14”. The number 18, written in base 5 is “33”, whose product of digits is 9, which is “14” in base 5. However, the number 17, written in base 6 is “25”, whose product of digits is 10, which is “14” is base 6.
To solve the problem, we iterate through every possible base, finding the smallest number in each base whose product of digits gives S. Since a number cannot exceed the product of its digits, we can stop when the string S evaluated in base B is greater than the smallest value of I found thus far. To find the smallest number in a fixed base, we use a modified Dijkstra’s algorithm.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.