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

13 Answers 13

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\$
  • 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 '11 at 12:43
  • \$\begingroup\$ @S.Mark, thanks. Looks like I can't get away with the naive factorisation algorithm. \$\endgroup\$ – Peter Taylor Apr 29 '11 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 '11 at 14:22
  • \$\begingroup\$ @mellamokb, good point. I think I'll have to rewrite and test. \$\endgroup\$ – Peter Taylor Apr 29 '11 at 14:50
  • \$\begingroup\$ Wow, 17 characters less. I need a better algorithm, lol! \$\endgroup\$ – mellamokb Apr 29 '11 at 23:14
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\$
  • \$\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 '11 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 '11 at 16:42
  • \$\begingroup\$ @fR0DDY: OK, now it's a complete program :) \$\endgroup\$ – mellamokb Apr 29 '11 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 '11 at 17:11
  • \$\begingroup\$ m?m:1 => m||1 \$\endgroup\$ – l4m2 May 3 '18 at 4:45
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\$
  • \$\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 '11 at 20:22
  • \$\begingroup\$ Also fails for input 1. Have to make a special case to handle 1. \$\endgroup\$ – mellamokb Apr 29 '11 at 20:25
  • \$\begingroup\$ I missed the "minimal" part, changed. \$\endgroup\$ – Ry- Apr 30 '11 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 '11 at 3:17
  • \$\begingroup\$ Ah, managed to make it 2 characters shorter than yours! :D \$\endgroup\$ – Ry- Apr 30 '11 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\$
  • \$\begingroup\$ We are calling program for one input only. Multiple inputs are given just to check correctness. \$\endgroup\$ – fR0DDY May 1 '11 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\$
  • \$\begingroup\$ Would it not be shorter if you used stdin instead of a parameter? \$\endgroup\$ – asoundmove May 1 '11 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\$
  • \$\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\$ – Peter Taylor Apr 29 '11 at 22:40
  • \$\begingroup\$ It also breaks for numbers divisible by primes greater than 9. \$\endgroup\$ – Peter Taylor Apr 29 '11 at 22:46
  • \$\begingroup\$ @Peter: OK, try again. I think this version works for all test cases now. \$\endgroup\$ – mellamokb Apr 29 '11 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\$ – Peter Taylor Apr 30 '11 at 7:22
  • \$\begingroup\$ @Peter: Thanks, saved 3 more chars! \$\endgroup\$ – mellamokb Apr 30 '11 at 14:34
3
\$\begingroup\$

Haskell

f n=head([m|m<-[1..10^9],product(map(read.return)$show m)==n]++[-1])
\$\endgroup\$
  • \$\begingroup\$ Shave off one char by changing (show m) to $show m. \$\endgroup\$ – FUZxxl Apr 30 '11 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 '11 at 9:35
  • \$\begingroup\$ I don't think it can work within 10secs.... \$\endgroup\$ – st0le May 1 '11 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\$
  • 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\$ – user202729 May 3 '18 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\$ – Harry May 3 '18 at 4:41
  • 1
    \$\begingroup\$ I think _¬$ should work over ’¹¬? \$\endgroup\$ – dylnan May 3 '18 at 4:50
  • 1
    \$\begingroup\$ o- is even shorter. \$\endgroup\$ – user202729 May 3 '18 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\$ – Harry May 3 '18 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, privacy policy and cookie policy

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