10
\$\begingroup\$

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
\$\endgroup\$
6
  • 4
    \$\begingroup\$ 1 giving 1 is an important test case. \$\endgroup\$ Apr 29, 2011 at 8:27
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – mellamokb
    Apr 29, 2011 at 14:23
  • \$\begingroup\$ @s-mark 26, eh. Smallest Number. \$\endgroup\$
    – fR0DDY
    Apr 29, 2011 at 17:03
  • \$\begingroup\$ I believe we should also test the obvious 387420489 (9^9) and 1000000000 for fun. \$\endgroup\$
    – asoundmove
    Apr 30, 2011 at 18:00
  • 2
    \$\begingroup\$ 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?) \$\endgroup\$
    – DELETE_ME
    May 3, 2018 at 3:51

13 Answers 13

6
\$\begingroup\$

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.

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

Golfscript, 45 43 40 chars

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

\$\endgroup\$
7
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – YOU
    Apr 29, 2011 at 12:43
  • \$\begingroup\$ @S.Mark, thanks. Looks like I can't get away with the naive factorisation algorithm. \$\endgroup\$ Apr 29, 2011 at 13:00
  • \$\begingroup\$ @Peter: Gives wrong answers for more complex cases. 32 -> 22222, should be 48. 432 -> 2222333, should be 689. 1296 -> 22223333, should be 2899. etc. \$\endgroup\$
    – mellamokb
    Apr 29, 2011 at 14:22
  • \$\begingroup\$ @mellamokb, good point. I think I'll have to rewrite and test. \$\endgroup\$ Apr 29, 2011 at 14:50
  • \$\begingroup\$ Wow, 17 characters less. I need a better algorithm, lol! \$\endgroup\$
    – mellamokb
    Apr 29, 2011 at 23:14
4
\$\begingroup\$

JavaScript, 88 72 78 74 69 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)
\$\endgroup\$
11
  • \$\begingroup\$ 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. \$\endgroup\$
    – mellamokb
    Apr 29, 2011 at 20:22
  • \$\begingroup\$ Also fails for input 1. Have to make a special case to handle 1. \$\endgroup\$
    – mellamokb
    Apr 29, 2011 at 20:25
  • \$\begingroup\$ I missed the "minimal" part, changed. \$\endgroup\$
    – Ry-
    Apr 30, 2011 at 0:46
  • \$\begingroup\$ @minitech: Still doesn't work for input '1'. lol, our answers are coming out to be almost exactly identical :-) \$\endgroup\$
    – mellamokb
    Apr 30, 2011 at 3:17
  • \$\begingroup\$ Ah, managed to make it 2 characters shorter than yours! :D \$\endgroup\$
    – Ry-
    Apr 30, 2011 at 3:41
4
\$\begingroup\$

awk (63 61 59 58 57)

{for(i=9;i>1;$1%i?i--:($1/=i)<o=i o);print 1<$1?-1:o?o:1}
\$\endgroup\$
1
  • \$\begingroup\$ We are calling program for one input only. Multiple inputs are given just to check correctness. \$\endgroup\$
    – fR0DDY
    May 1, 2011 at 5:01
3
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ Would it not be shorter if you used stdin instead of a parameter? \$\endgroup\$
    – asoundmove
    May 1, 2011 at 9:02
3
\$\begingroup\$

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.

\$\endgroup\$
13
  • \$\begingroup\$ 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. \$\endgroup\$ Apr 29, 2011 at 22:40
  • \$\begingroup\$ It also breaks for numbers divisible by primes greater than 9. \$\endgroup\$ Apr 29, 2011 at 22:46
  • \$\begingroup\$ @Peter: OK, try again. I think this version works for all test cases now. \$\endgroup\$
    – mellamokb
    Apr 29, 2011 at 23:11
  • \$\begingroup\$ 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 $. \$\endgroup\$ Apr 30, 2011 at 7:22
  • \$\begingroup\$ @Peter: Thanks, saved 3 more chars! \$\endgroup\$
    – mellamokb
    Apr 30, 2011 at 14:34
3
\$\begingroup\$

Haskell

f n=head([m|m<-[1..10^9],product(map(read.return)$show m)==n]++[-1])
\$\endgroup\$
3
  • \$\begingroup\$ Shave off one char by changing (show m) to $show m. \$\endgroup\$
    – FUZxxl
    Apr 30, 2011 at 13:24
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – st0le
    May 1, 2011 at 9:35
  • \$\begingroup\$ I don't think it can work within 10secs.... \$\endgroup\$
    – st0le
    May 1, 2011 at 9:37
2
\$\begingroup\$

Windows PowerShell, 87

if(($n="$args")-le1){$n;exit}(-1,-join(9..2|%{for(;!($n%$_)){$_;$n/=$_}}|sort))[$n-eq1]
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 18 13 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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – DELETE_ME
    May 3, 2018 at 3:59
  • \$\begingroup\$ @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? \$\endgroup\$
    – habs
    May 3, 2018 at 4:41
  • 1
    \$\begingroup\$ I think _¬$ should work over ’¹¬? \$\endgroup\$
    – dylnan
    May 3, 2018 at 4:50
  • 1
    \$\begingroup\$ o- is even shorter. \$\endgroup\$
    – DELETE_ME
    May 3, 2018 at 5:20
  • \$\begingroup\$ @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! \$\endgroup\$
    – habs
    May 3, 2018 at 5:42
1
\$\begingroup\$

Ruby (100)

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.