SPOJ.com - Problem SNGINT

SNGINT - Encode Integer

Given an integer N (0 <= N < 10⁷), find the smallest positive integer M (M > 0) such that the product of digits of M equals N.

The first line of input is T (the total number of test cases), followed by T (T < 10001) lines, each containing an integer N.

For each integer N, output in a separate line the integer M, or -1 (if encoding is not possible).

Input:
3
24
5
11

Output:
38
5
-1



2020-06-08 14:21:40 don't think so hard answer for n=0 is 10 Finally,got it after lots of WA bruteforcing lol Last edit: 2020-06-08 14:21:59
2019-03-14 14:35:10 You just need to think about this for a little time. The logic will come on its own. It was a nice one, costed me one WA This is just a challenge for the people who solved this: Try doing it in < O(N) time. Last edit: 2019-03-15 19:50:44
2018-12-10 10:28:14 When n=0, ans is not 0... it is next smallest integer..
2018-07-15 01:22:51 Take care of the case n=0
2015-05-08 19:31:26 Vipul Srivastava Nice one..
2014-11-27 11:57:13 Deepak Gupta I think "another possible" should be removed, as the answer can be same, as in the given examples.
2014-11-09 15:15:59 numerix @Deepak Gupta: According to the problem description ("product") you are right. A product needs at least two factors and m=5 is only a single number. On the other hand: The example (n=5 -> m=5) makes it clear how to handle these cases. I got AC with that assumption.
2014-11-09 09:37:07 Deepak Gupta Shouldn't the answer for 5 be 15??
2014-02-14 16:37:41 Mitch Schwartz It is also my opinion that the source limit is unnecessarily small, although of course it's not a huge obstacle. I knew at time of submission that there is a quite short way to solve this, but it is also slower than what I did. So my code is just a little mutilated to pass the source limit.