A vintage slot machine displays its payout multiplier as a numeric code made only of the digits 1 through 9 (a 0 digit would zero out the payout, so it never appears on the display). The multiplier shown by a code equals the product of its digits — for example the code 68 shows a multiplier of 6 x 8 = 48.
Given a target payout multiplier, find the smallest positive integer code whose digits multiply together to exactly that target. If the smallest such code would exceed the range of a 32-bit signed integer (greater than 2147483647), or if no combination of digits 1-9 can multiply together to reach the target at all, report 0 instead.
A single line containing one integer n, the target payout multiplier.
A single integer: the smallest positive code whose digits multiply to n, or 0 if no such code exists within the 32-bit signed integer range.
Example 1
Input
48
Expected
68
Explanation
The digits must multiply to 48. Using digits 6 and 8 (6 x 8 = 48) gives the two-digit code "68" once the digits are arranged in ascending order to form the smallest possible code. No single digit reaches 48 (since 48 > 9), and no other two-digit digit combination multiplies to 48 with a smaller arrangement, so 68 is the answer.
Example 2
Input
1
Expected
1
Explanation
The only digit combination whose product is 1 is the single digit "1" itself (a code must have at least one digit), so the smallest valid code is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →