35
\$\begingroup\$

I have come across a question on the Code Review site that seems interesting. I think OP is doing it wrong, but cannot be sure... So let's solve it for him! (write a program, not a function/procedure)

Input (stdin or similar):

An integer x in decimal notation. It is greater than 1 and less than 2^31.

Output (stdout or similar):

An integer y in decimal notation. The product x * y in decimal representation must contain only digits 0 and 1. It must be the minimal such number greater than 0.

Note: output is not limited - if the minimal y is around 10^100, your program must output all of its 100 digits (I don't know whether there is a reasonable limit, like 2^64, on y - didn't solve it).

Your program should finish in a reasonable time (1 second? 1 hour? - something like that) for all x in range.

Bonus:

If your program doesn't have a limit on the size of the input (except RAM), and has polynomial complexity, multiply the byte count of your program by 0.8 and round down.


Example: Input 2; output 5, because 2 * 5 = 10

Example: Input 21; output 481, because 21 * 481 = 10101


Disclaimer: I am not responsible for the question on the Code Review site. In case of any discrepancy, only the description above should be regarded as proper spec.

OEIS A079339

\$\endgroup\$
19
  • 6
    \$\begingroup\$ It should always be solvable. Clearly there must exist at least one q such that there are an infinite number of n such that 10^n mod x = q. Take x such values of n and add together the respective powers 10^n. \$\endgroup\$ Commented Oct 15, 2015 at 21:57
  • 1
    \$\begingroup\$ Multiples of 9 seem to produce unusually high results. \$\endgroup\$ Commented Oct 16, 2015 at 2:02
  • 1
    \$\begingroup\$ Related Project Euler problem, for anyone else who thought this question looked familiar \$\endgroup\$ Commented Oct 16, 2015 at 2:42
  • 2
    \$\begingroup\$ By polynomial complexity, do you mean polynomial in the number of digits of the input, or polynomial in the value of the input? \$\endgroup\$ Commented Oct 16, 2015 at 3:48
  • 3
    \$\begingroup\$ @anatolyg mine is not brute force \$\endgroup\$ Commented Oct 16, 2015 at 16:29

44 Answers 44

1
2
1
\$\begingroup\$

Dyalog APL, 25

This defines a proper program "P" (not just an unnamed function):

P←2∘{0::⍵∇⍨1+⍺⋄⍺⊣~⍎¨⍕⍺×⍵} 

2∘ begin with 2 as left argument
0:: if there is any error...
⍵∇⍨1+⍺ call itself with an incremented left argument
⍺×⍵ multiply left and right arguments
make into string
⍎¨ make each character into a number
~ attempt logical NOT (if it fails, go to error-handling above, else...)
⍺⊣ return the current left argument.

 P 2 50 P 21 481 P¨⍳8 ⍝ 1 through 8 10 5 37 25 2 185 143 125 
\$\endgroup\$
1
\$\begingroup\$

Jelly, 8 bytes

×QḌ=⁵ð1# 

Try it online!

Tied Pyth!

How it works

×QḌ=⁵ð1# - Main link. Takes n on the left ð - Combine the previous links into a dyad f(i, n): × - i×n Q - Unique digits Ḍ - Convert into an integer =⁵ - Does this equal 10? f(i, n) returns true for a given i if i×n only consists of 1 and 0 1# - Starting from n, find the first integer i = n, n+1, ... such that f(i, n) is true 
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 13 bytes

∞›*'S₀S↔=;h$/ 

Try it Online!

∞›* # All multpiles of n ' ; # Filtered by S₀S↔ # When you remove all the digits except 0 and 1 = # Does it equal itself? h # Get the first item for which this happens $/ # Divide by n 
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 82 bitsv2, 10.25 bytes

¨*'₀τGċ¬;h?/ 

Try it Online!

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 44 bitsv2, 5.5 bytes

?*↑ṅ)ṅ 

Try it Online!

\$\endgroup\$
1
\$\begingroup\$

Thunno 2, 4 bytes

Ƙ×Gḅ 

Try it online!

Explanation

Ƙ×Gḅ # Implicit input Ƙ # First integer where: × # Multiply by the input G # Maximum digit ḅ # Equals one? # Implicit output 
\$\endgroup\$
1
\$\begingroup\$

PowerShell Core, 35 bytes

for(;++$i*"$args"-replace"0|1"){}$i 

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C#, 156+31=187 bytes

The code requires the following usings:

using System;using System.Linq; 

Here the code:

class P{static void Main(string[]a){var b=ulong.Parse(Console.ReadLine());var d=1U;for(;(b*d).ToString().Any(x=>x!='0'&&x!='1');d++);Console.WriteLine(d);}} 

Ungolfed:

using System; using System.Linq; class P { static void Main(string[] a) { var b = ulong.Parse(Console.ReadLine()); var d = 1U; for (; (b*d).ToString().Any(x => x != '0' && x != '1'); d++); Console.WriteLine(d); } } 
\$\endgroup\$
0
\$\begingroup\$

SAS, 81 bytes

This is give or take the same approach as some of the 'fast' python approaches above: iterate through the possible binary numbers, pretend they're decimal, test them.

data a;b=72;do until(a=int(a));y+1;a=input(put(y,binary32.),32.)/b;end;put a;run; 

Unfortunately I can't skip the input/put, because the default width for implicit conversions is only 12 (meaning it quickly becomes "1e8" and similar which fails).

Ungolfed:

data a; b=72; do until(a=int(a)); y+1; a=input(put(y,binary32.),32.)/b; end; put a; run; 

This isn't entirely safe; for larger numbers (which have no solution in a double precision floating point environment) this could turn into an infinite loop.

\$\endgroup\$
0
\$\begingroup\$

Ruby 46 bytes

No better in # of bytes than the previous Ruby solution by the Peter Lenkefi, but slightly different approach:

gets;p 1.step.find{|i|"#{$_.to_i*i}"!~/[^01]/} 
\$\endgroup\$
0
\$\begingroup\$

Burlesque, 24 bytes

Found a shorter version:

1R@?*b0{{"10"j~[}al}fi?i 

Older Versions:

1R@?*b0{"\`[01]*\\'"~=}fi?i 

It's terribly slow though if the number can't be found fast.

1R@?*b0{"23456789"INnu}fi?i 

This version might be faster because it doesn't use regexes. Still terribly slow though.

There's no limit except the time it takes to find the answer which can be quite long.

\$\endgroup\$
0
\$\begingroup\$

Husk, 9 bytes

ḟö=1▲d*⁰N 

Try it online!

ḟö=1▲d*⁰N ḟö # first truthy element of: *⁰N # multiply all natural numbers by input ▲d # max of decimal digits =1 # equals 1 
\$\endgroup\$
0
\$\begingroup\$

Japt, 13 12 10 bytes

È*U skA}f1 

Try it - Be careful with multiples of 9 ;)

\$\endgroup\$
0
\$\begingroup\$

Ruby, 36 bytes

->n{(1..).find{(_1*n).digits.max<2}} 

Attempt This Online!

\$\endgroup\$
1
2

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.