34
\$\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\$
  • 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\$ – feersum Oct 15 '15 at 21:57
  • 1
    \$\begingroup\$ Multiples of 9 seem to produce unusually high results. \$\endgroup\$ – SuperJedi224 Oct 16 '15 at 2:02
  • 1
    \$\begingroup\$ Related Project Euler problem, for anyone else who thought this question looked familiar \$\endgroup\$ – Sp3000 Oct 16 '15 at 2:42
  • 1
    \$\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\$ – Reto Koradi Oct 16 '15 at 3:48
  • 3
    \$\begingroup\$ @anatolyg mine is not brute force \$\endgroup\$ – aditsu Oct 16 '15 at 16:29

36 Answers 36

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\$

Pyth, 8 bytes

fq`;{`*Q

Try it here.


How?

fq`;{`*Q   - Full program.

f          - First input where the condition is truthy over [1, ∞)
      *Q   - The product of the input and the current number
     `     - Converted to String.
    {      - Deduplicated.
 q         - Is equal to?
  `;       - The string representation of the innermost lambda variable, T, which is "10".
           - Output implicitly.

This pretty much relies on the fact that numbers do not have trailing zeros, and 1 always occurs before 0 in a positive integer only consisting of 0s and 1s.

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

Japt, 13 12 bytes

È*U ì e<2}a1

Try it - Be careful with multiples of 9 ;)


Alternative

@*X ìâ ¥A}a1
\$\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.