# Product of Digits

For a given positive integer number N, write a complete program to find the minimal natural M such that the product of digits of M is equal N. N is less than 1,000,000,000. If no M exists, print -1. Your code should not take more than 10 secs for any case.

Sample Inputs
1
3
15
10
123456789
32
432
1296

Sample Outputs
1
3
35
25
-1
48
689
2899

• 1 giving 1 is an important test case. Commented Apr 29, 2011 at 8:27
• You should add more complex cases, like the three I've used below: 32, 432, 1296. Unless you leave that as an exercise for the coder. Commented Apr 29, 2011 at 14:23
• @s-mark 26, eh. Smallest Number. Commented Apr 29, 2011 at 17:03
• I believe we should also test the obvious 387420489 (9^9) and 1000000000 for fun. Commented Apr 30, 2011 at 18:00
• Because this is an old question and the OP is inactive, this is just a note for future posts: "10 sec" is unclear according to the current standard (on which machine?) Commented May 3, 2018 at 3:51

## Javascript (84 78 76 74 72 70 68)

n=prompt(m="");for(i=9;i-1;)n%i?i--:(m=i+m,n/=i);alert(n-1?-1:m?m:1)


http://jsfiddle.net/D3WgU/7/

Edit: Borrowed input/output idea from other solution, and shorter output logic.

Edit 2: Saved 2 chars by removing unneeded braces in for loop.

Edit 3: Saved 2 chars by rewriting while loop as if statement with i++.

Edit 4: Saved 2 chars by moving around and reducing operations on i.

Edit 5: Convert if statement into ternary format saving 2 more chars.

Edit 6: Save 2 chars by moving i-- into true part of ternary, remove ++i.

• You have counted characters for just the function. Is this a complete program? Can you execute it here ideone.com Commented Apr 29, 2011 at 15:06
• looks like there is similar input for javascript with spidermonkey at ideone he linked - ideone.com/samples#sample_lang_112
– YOU
Commented Apr 29, 2011 at 16:42
• @fR0DDY: OK, now it's a complete program :) Commented Apr 29, 2011 at 20:30
• I finally reduced mine to 69 characters, but you can do that too now with the same sort of idea and the prompt thing.
– Ry-
Commented Apr 30, 2011 at 17:11
• m?m:1 => m||1
– l4m2
Commented May 3, 2018 at 4:45

~9{{1$1$%!{\1$/1$}*}12*(}8*>{];-1}*]$1or  Replaces version which didn't group small primes into powers and saves 8 chars while doing so. Note: 12 = floor(9 log 10 / log 5). Acknowledgements: two characters saved by nicking a trick from @mellamokb; 3 saved with a hint from @Nabb. • What! You can write Golfscript without testing it? +1, Looks fine, except 123456789, its take more than 1 minute on my machine and I've killed the process. 12345 give me -1, so may be it should work for 123456789 too if I could wait long time enough. – YOU Commented Apr 29, 2011 at 12:43 • @S.Mark, thanks. Looks like I can't get away with the naive factorisation algorithm. Commented Apr 29, 2011 at 13:00 • @Peter: Gives wrong answers for more complex cases. 32 -> 22222, should be 48. 432 -> 2222333, should be 689. 1296 -> 22223333, should be 2899. etc. Commented Apr 29, 2011 at 14:22 • @mellamokb, good point. I think I'll have to rewrite and test. Commented Apr 29, 2011 at 14:50 • Wow, 17 characters less. I need a better algorithm, lol! Commented Apr 29, 2011 at 23:14 ## JavaScript, 8872787469 68 for(s='',i=2,m=n=prompt();i<m;i++)while(!(n%i)){if(i>9){alert(-1);E()}n/=i;s+=i}alert(s) 4 characters longer, but actually an executable script (as opposed to a function). Edit: Using ideas from the other JavaScript, I can reduce it to this: for(s='',i=9,n=prompt();i>1;i--)for(;!(n%i);n/=i)s=i+s;alert(n-1?-1:s?s:1)  Finally! A 69-character solution, only uses 1 for loop ;) for(s='',i=9,n=prompt();i>1;n%i?i--:[n/=i,s=i+s]);alert(n-1?-1:s?s:1)  Okay, shaved off one comma. for(i=9,n=prompt(s='');i>1;n%i?i--:[n/=i,s=i+s]);alert(n-1?-1:s?s:1)  • Same problem as GolfScript solution. Fails on inputs 32, 432, and 1296. There's a reason why I start at 9 and go backwards, and concatenate from the right instead of the left. Commented Apr 29, 2011 at 20:22 • Also fails for input 1. Have to make a special case to handle 1. Commented Apr 29, 2011 at 20:25 • I missed the "minimal" part, changed. – Ry- Commented Apr 30, 2011 at 0:46 • @minitech: Still doesn't work for input '1'. lol, our answers are coming out to be almost exactly identical :-) Commented Apr 30, 2011 at 3:17 • Ah, managed to make it 2 characters shorter than yours! :D – Ry- Commented Apr 30, 2011 at 3:41 ## awk (63615958 57) {for(i=9;i>1;$1%i?i--:($1/=i)<o=i o);print 1<$1?-1:o?o:1}

• We are calling program for one input only. Multiple inputs are given just to check correctness. Commented May 1, 2011 at 5:01

## Perl (75) (72)

$d=shift;map{$m=$_.$m,$d/=$_ until$d%$_}reverse 2..9;print$d-1?-1:$m||1


inspired by mellamokb's javascript code; meant to be run with a parameter

• Would it not be shorter if you used stdin instead of a parameter? Commented May 1, 2011 at 9:02

## GolfScript (60 57)

~[{9,{)}%{\.@%!},)\;.@@/.9>2$1>&}do])[.])@@{1>},+\9>[-1]@if$


~{9,{)}%{\.@%!},)\;.@@/.9>2$1>&}do])[.])@@{1>},+$\9>-1@if


Edit

Ok, I think this version gives correct output for every case now :-)

Edit 2

Shaved off 3 chars per @Peter's suggestions.

• The reason I commented above that 1 giving 1 is an important test case is that it's a nasty special case - the only number for which the digit 1 appears in the output. And it breaks your code, I'm afraid. Commented Apr 29, 2011 at 22:40
• It also breaks for numbers divisible by primes greater than 9. Commented Apr 29, 2011 at 22:46
• @Peter: OK, try again. I think this version works for all test cases now. Commented Apr 29, 2011 at 23:11
• Seems to, yes. You can save one character straight away by removing that first [ - if you don't have a [ on the stack when you evaluate a ] it takes everything on the stack. And you can probably save two characters near the end by not wrapping -1 in an array and moving the final $. Commented Apr 30, 2011 at 7:22 • @Peter: Thanks, saved 3 more chars! Commented Apr 30, 2011 at 14:34 ## Haskell f n=head([m|m<-[1..10^9],product(map(read.return)$show m)==n]++[-1])

• Shave off one char by changing (show m) to $show m. Commented Apr 30, 2011 at 13:24 • shouldn't it be m<-[1..9^9]....otherwise it's an infinite list...so -1 will never occur....correct me if i'm wrong. Commented May 1, 2011 at 9:35 • I don't think it can work within 10secs.... Commented May 1, 2011 at 9:37 ## Windows PowerShell, 87 if(($n="$args")-le1){$n;exit}(-1,-join(9..2|%{for(;!($n%$_)){$_;$n/=$_}}|sort))[$n-eq1]


# Perl (68)

$x=pop;map{$_-=11;$x/=$_,$@=-$_.$@until$x%$_}1..9;print!$x?-1:$@||1  It seems like the awesome trick that @mellamokb uses in javascript to avoid the nested loop would translate well to perl but it comes out much more verbose because you cannot use the foreach style loop any longer. It's also a pity that perl does not think map is a loop else redo would come in handy. ### scala 106 chars: def p(n:Int,l:Int=9):List[Int]=if(n<=9)List(n)else if(l<2)List(-1)else if(n%l==0)l::p(n/l,l)else p(n,l-1)  Test & Invocation: scala> val big=9*9*9*8*8*8*7*7*7*5*3 big: Int = 1920360960 scala> p(big) res1: List[Int] = List(9, 9, 9, 8, 8, 8, 7, 7, 7, 5, 3)  Response time: immediately, < 1s on 2Ghz CPU. # Jelly, 1813 10 bytes ×⁵RDP$€io-


Try it online!

13-byte solution:

×⁵RDP$€iµ’¹¬?  Try it online! Explanation with input N: ×³R create a range from 1 to N * 100 (replace ³ with ⁵ for a faster execution time) DP$           define a function ($) to get the product of the digits of a number, € apply that function to each element in the list, iµ get the index of the input N in the list (or 0 if it's not there), and yeild it as the input to the next link, ’¹¬? conditional: if the answer is 0, then subtract one to make it -1, otherwise, yeild the answer  18-byte solution: D×/ ×⁵RÇ€i Ç⁾-1¹¬?  Try it online! D×/ product of digits function, takes input M D split M into digits, ×/ reduce by multiplication (return product of digits) ×⁵RÇ€i range / index function ×⁵R make a range from 1 to N*10, Ç€ run the above function on each of the range elements, i get the index of N in the result, or 0 if it's not there Ç⁾-1¹¬? main function: Ç ¬? run the line above and check if the answer is null (0) ⁾-1 if it is, return "-1", ¹ otherwise, return the answer (identity function).  The last link is only to replace 0 (Jelly's default falsey value, as all lists are one-indexed) with -1. If you consider 0 an OK falsey value, the program is 8 bytes. • Some notes: (1) you use each auxiliary link only once, so there is no reason to make auxiliary link. Just use the $ƊƲµ. (2) As the string -1 and the number -1 is identical when output, using the number saves 2 bytes. (3) P is shorthand for ×/. (4) Fails for input 3125. Commented May 3, 2018 at 3:59
• @user202729 Thank you so much! I implemented (1), (2), and (3) and they saved 6 bytes! If I changed the ⁵ to a ³, it worked on input 3125 but only after a considerable delay. Do you know if there's a better (and shorter) way, or is my approach (which I know is definitely not the fastest in terms of time-complexity) as good as it will get?
– habs
Commented May 3, 2018 at 4:41
• I think _¬$ should work over ’¹¬? Commented May 3, 2018 at 4:50 • o- is even shorter. Commented May 3, 2018 at 5:20 • @dylnan Thank you -- I noticed that because of the µ I could just use _¬ without the $ which saved 2 bytes! But then I realized with o- I could just omit the µ entirely and save 3 bytes!
– habs
Commented May 3, 2018 at 5:42

## Ruby (100)

n=gets.to_i;(d=1..9).map{|l|[*d].repeated_combination(l){|a|a.reduce(:*)==n&&(puts a*'';exit)}};p -1


# Python 2, 89 bytes

f=lambda n,a=0,u=1,i=9:n<2and(a or 1)or-(i<2)or n%i<1and f(n/i,a+i*u,u*10)or f(n,a,u,i-1)


Try it online!

Just because there's no Python answer yet. It's really painful to lack implicit type conversion between string and int.