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

44 Answers 44

20
\$\begingroup\$

Python 2, efficient solution, 99

n=input()
d={n:0}
k=1
while min(d):[d.setdefault((x+k)%n,d[x]+k)for x in set(d)];k*=10
print d[0]/n

Thanks Sp3000 for some golfing tips.

I challenge everybody else to post (in their own answers) how long it takes to get the result for input 72 or 99 :) If those are really fast, try something like 79992 next (still <1 sec here).

Explanation:

I thought this wasn't necessary (since the code is fairly readable), but I got a request, so here it goes:

The first idea is that a binary-looking number is a sum of 1 or more different powers of 10. Therefore, we can try to add various powers of 10 in different ways until we get remainder 0.

If we do that naively, it's the same as generating all binary-looking numbers and testing them. But a lot of remainders will be the same. A better way is to record only the smallest number that gave a certain remainder, and successively add greater powers of 10 to numbers we recorded. That's what the program does.

d is a dictionary/map where keys are remainders and values are binary-looking numbers with that remainder. The initial n:0 is a special case: it's supposed to be 0:0 so we can start adding powers to it, but the algorithm stops when finding key 0, so I used n instead, which is guaranteed to have the same effect and not interfere with the other values.

Then we start adding powers of 10 (stored in k) to all existing numbers and recording the remainders. We add k to the remainder: (x+k)%n and to the number: d[x]+k, and record it only if it's a new remainder: d.setdefault(…), then go to the next power: k*=10 and repeat until we get key 0: while min(d)

At the end, d[0] gives the binary-looking number that has remainder 0 mod n, so we divide it by n to get the solution.

Note: the program can be made more efficient by avoiding large numbers (recording exponents rather than powers of 10, and calculating remainders of powers from previous values), but it's code golf, so...

In fact, here, I wrote a faster version:

n=input()
d={n:0}
k=1
b=0
while 0not in d:
 for x in list(d):d.setdefault((x+k)%n,b)
 k=(k*10)%n;b+=1
x=10**d[0]
while x%n:x+=10**d[n-x%n]
print x/n
\$\endgroup\$
12
  • 1
    \$\begingroup\$ My answer doesn't get either. xD "Dangit, Java, curse thy choice of Integer.MAX_VALUE over using BigInteger by default!" - Every Java Programmer Ever \$\endgroup\$ Oct 16, 2015 at 16:25
  • \$\begingroup\$ @VTCAKAVSMoACE why don't you use Long? \$\endgroup\$ Oct 16, 2015 at 16:28
  • \$\begingroup\$ Hmm. It's an extra byte, but... worth it. Thanks! \$\endgroup\$ Oct 16, 2015 at 16:28
  • \$\begingroup\$ Or not. That actually seriously reduces it. Thanks! \$\endgroup\$ Oct 16, 2015 at 16:30
  • 1
    \$\begingroup\$ Timings for solving 99: aditsu: 0.001 seconds; xnor: 5+ hours and it still didn't complete. \$\endgroup\$
    – user193661
    Oct 17, 2015 at 2:40
12
\$\begingroup\$

Python 2, 47 bytes

n=a=input()
while'1'<max(str(a)):a+=n
print a/n

Tracks the input number n and the current multiple a. When a looks like binary, output the ratio a/n. To check that a number is made of 0's and 1's, we compare the maximum char in its string representation to '1'.

Uses str(a) instead of `a` to avoid longs ending in L. Unfortunately, 'L' is bigger than '1'.

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

Perl, 27 bytes

#!perl -p
1while($_*++$\)=~/[2-9]/}{

Counting the shebang as one, input is taken from stdin.

Sample Usage

$ echo 2 | perl dec-bin.pl
5

$ echo 21 | perl dec-bin.pl
481

$ echo 98 | perl dec-bin.pl
112245

Perl, 25 bytes

#!perl -p
eval'0b'.++$\*$_||redo}{

A two byte improvement by @skmrx.

Rather than checking against a regex, this instead attempts to evaluate the product as a binary literal. Upon failure, it moves on to the next. Typically the oct function would be used for this purpose, but it silently trims invalid digits, which isn't useful in this challenge.


Perl, 40 bytes

#!perl -p
1while($b=sprintf"%b",++$i)%$_;$_=$b/$_

A far more efficient solution. We iterate over binary representations, interpret them as base 10, and then check for divisibility. Runtimes for all values under 100 are negligible.

Sample Usage

$ echo 72|perl dec-bin.pl
1543209875

$ echo 99|perl dec-bin.pl
1122334455667789
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Nice :) I learnt a couple of new things from your post today! While reading through your code, I found a way to shave off a couple of bytes from the first code: eval"0b".$_*++$\||redo}{ \$\endgroup\$
    – svsd
    Oct 17, 2015 at 23:11
  • \$\begingroup\$ But I guess we'll need to include use bigint to support the large numbers that OP has mandated to be supported :( \$\endgroup\$
    – svsd
    Oct 17, 2015 at 23:31
  • 1
    \$\begingroup\$ @skmrn That's brilliant. I had tried oct'0b'.++$\*$_, but it silently trims invalid digits. I didn't think to use eval instead. \$\endgroup\$
    – primo
    Oct 18, 2015 at 7:46
12
\$\begingroup\$

Javascript, 43 bytes

This ended up way shorter than I thought. It basically increments y up 1 until y * (input number) = (binary-looking number). Obviously quite inefficient.

for(x=prompt(y=0);!+('0b'+x*++y););alert(y)


Javascript (more efficient solution), 53 bytes

This one increments y in binary until y / (input number) = (number without a remainder). Then it outputs (number without a remainder).

for(x=prompt(y=1);(z=y.toString(2))%x;y++);alert(z/x)


Javascript (even more efficient solution), 76 bytes

This one combines both of the previous methods described above. It checks increments y until either y * (input number) = (binary-looking number) (meaning that the output is y) OR y / (input number) = (number without a remainder) (meaning that the output is (number without a remainder)).

for(x=prompt(y=a=0);!a;a=+('0b'+x*++y)?y:(z=y.toString(2))%x?0:z/x);alert(a)

\$\endgroup\$
6
  • \$\begingroup\$ It should give 1 when possible (example input: 1) \$\endgroup\$
    – edc65
    Oct 16, 2015 at 12:55
  • \$\begingroup\$ @edc65 Fixed - with no change in byte count! \$\endgroup\$ Oct 16, 2015 at 13:23
  • \$\begingroup\$ This crashes Safari 9.0. Jussayin'. :) \$\endgroup\$ Oct 16, 2015 at 16:28
  • 1
    \$\begingroup\$ But it's limited to small numbers in output. Javascript numbers have 17 digits of precision, OP is asking for something bigger (and it can be done using modular arithmetic) \$\endgroup\$
    – edc65
    Oct 16, 2015 at 23:59
  • \$\begingroup\$ Protip: Don't try input 72. Firefox 41 freezes up for 15 minutes and then crashes. I discovered this the hard way. \$\endgroup\$ Oct 17, 2015 at 18:21
9
\$\begingroup\$

Haskell, 72 70 64 60 58 bytes

main=do x<-readLn;print$[y|y<-[1..],all(<'2')$show$x*y]!!0

Edit: @Jan Dvorak helped me saving 4 bytes.

Edit: @BlackCap saved 2 bytes by switching to do notation. Thanks!

\$\endgroup\$
4
  • \$\begingroup\$ main=print.f=<<readLn \$\endgroup\$ Oct 18, 2015 at 23:18
  • \$\begingroup\$ You can save a byte by inlining f: main=readLn>>= \x->print$[y|y<-[1..],all(<'2')$show$x*y]!!0 \$\endgroup\$
    – BlackCap
    Oct 25, 2016 at 0:14
  • \$\begingroup\$ 2 actually main=do x<-readLn;print$[y|y<-[1..],all(<'2')$show$x*y]!!0 \$\endgroup\$
    – BlackCap
    Oct 25, 2016 at 0:17
  • \$\begingroup\$ @BlackCap: Nice! Thanks a lot! \$\endgroup\$
    – nimi
    Oct 25, 2016 at 6:04
8
\$\begingroup\$

Pyth, 9 bytes

f!-`*TQ10

Demonstration

For each multiple, convert to a string, subtract out the digits in 10 (using Pyth's handy int to str cast in this case) and then logically negate the result, terminating the seach only when the correct multiple is found.

Bonus solution, 10 bytes:

f.xi`*TQ2Z

This solution actually checks if the string representation of the number can be treated as a binary number (i ... 2) and terminates when an error is not thrown on this attempt.

\$\endgroup\$
7
\$\begingroup\$

Python 2, 67 65 63 60 bytes

a=input();b=1
while set(`a*b`)&set('23456789'):b+=1
print b

Thanks to Status for 2 bytes and Shebang for 5 bytes!

\$\endgroup\$
13
  • 1
    \$\begingroup\$ I think you must initialize b=1 \$\endgroup\$
    – anatolyg
    Oct 15, 2015 at 22:15
  • 2
    \$\begingroup\$ You can shave 2 bytes by doing any(c in`a*b`for c in'23456789') \$\endgroup\$
    – Status
    Oct 15, 2015 at 22:33
  • 1
    \$\begingroup\$ I'm not sure about this but would not c in`a*b`for c in'10' work? \$\endgroup\$
    – cole
    Oct 15, 2015 at 22:38
  • 2
    \$\begingroup\$ You can save 6 bytes by changing your while condition to set('a*b')&set('23456789'). \$\endgroup\$
    – Kade
    Oct 15, 2015 at 23:07
  • 2
    \$\begingroup\$ ` produces an L for longs and 'L'>'1'. \$\endgroup\$
    – user193661
    Oct 15, 2015 at 23:34
6
\$\begingroup\$

JavaScript (ES6) 222 250

Using arbitrary precision math (operating on strings of decimal digits)

This can be golfed a little more(done), but I like the fact that it is not limited to JS standard numbers (17 decimal digits of precision) and that it is fast.

Test running the snippet below in an EcmaScript 6 compliant browser. Time is acceptable up to 9998 - don't try 9999 and be patient with 999.

// As a complete program with I/O via popup  
for(n=+prompt(a=[0],q=[t=1]);t;){for(c=1,t=i=0;i<a.length;i++)a[i]=a[i]&c?0:a[i]|c?(c=0,t+=q[i],1):c=0;c&&(a[i]=c,t+=q[i]=q[i-1]*10%n);t%=n}a.reverse().map(a=>(z+=[a],d=z/n|0,z%=n,r||d?r+=d:0),r='',z=0);alert([r,a.join``])

// As a testable function
f=n=>{
  for(a=[0],q=[t=1];t;)
  {
    for(c=1,t=i=0;i<a.length;i++)
      a[i]=a[i]&c?0:a[i]|c?(c=0,t+=q[i],1):c=0
    c&&(a[i]=c,t+=q[i]=q[i-1]*10%n);
    t%=n
  }  
  a.reverse().map(a=>(z+=[a],d=z/n|0,z%=n,r||d?r+=d:0),r='',z=0)
  return [r,a.join``]
}

// Test and timing
out = x => O.innerHTML += x + '\n'

setTimeout(_=>{
;[1,2,10, 21, 23, 98, 72, 9, 99, 999]
.forEach((test,i) => { 
  var t0 = ~new Date  
  var result = f(test)
  out('n='+test+' '+result+' time(ms) ' + (t0-~new Date))
})},100)  
<pre id=O>Timing test cases ...
</pre>

More readable

This is the first version, with modulus and long division as separated functions.

// function M - Modulus with arbitrary precision - a is a string of decimal digits
M = (a, b, q = 1, t = 0, j = a.length) => {
  while (j--) + a[j] ? t += q : 0, q = (q * 10) % b;
  return t % b
}

// function D - Long division with arbitrary precision - a is a string of decimal digits
D = (a, b, r = '', z = 0) => [...a].map(a => (z += a, d = z / b | 0, z %= b, r || d ? r += d : 0)) && r

// Testable function 
f = n => {
  for (i = 0; ++i < 1e7 && (z = M(v = i.toString(2), n)););
  return z ? ['big'] : [D(v, n), v]
}
\$\endgroup\$
4
  • \$\begingroup\$ I got it to work in Firefox, but it doesn't seem handle bigger numbers, e.g. 999 \$\endgroup\$ Oct 17, 2015 at 15:50
  • \$\begingroup\$ I'have a new version that can handle 999 in 36 seconds, but there's no hope to reach 9999 with the javascript timeout (each '9' added require 2^9 (~500) times the time to finish) \$\endgroup\$
    – edc65
    Oct 17, 2015 at 16:43
  • \$\begingroup\$ @aditsu that's the best I can do in JavaScript (but in C# it's quite the same). Eaherly waiting for an explanation of you incredible algorithm \$\endgroup\$
    – edc65
    Oct 17, 2015 at 21:44
  • \$\begingroup\$ I added an explanation now \$\endgroup\$ Oct 17, 2015 at 22:40
5
\$\begingroup\$

Perl, 45 bytes

do{$a++}while($a*($b||=<>))=~/[2-9]/;print$a;
\$\endgroup\$
5
\$\begingroup\$

Python 3 2, 101 76 Bytes

-25 bytes thanks to @aditsu

almost as efficient as @aditsu's solution

99 -> 0.436 Seconds
72 -> 0.007 Seconds
b,m,n=1,1,input()
while b%n:
 b=int("{0:b}".format(m))
 m+=1
print b/n

Instead of trying to loop through the multiples in increasing order, I'm trying to loop through the products, which I'm generating in 'binary' form.

\$\endgroup\$
4
  • \$\begingroup\$ Not bad :) What about 9999? \$\endgroup\$ Oct 17, 2015 at 15:37
  • 2
    \$\begingroup\$ Some golfing tips: use python 2 (n=input()), while b%n: (initialize b to 1), no indentation \$\endgroup\$ Oct 17, 2015 at 15:40
  • \$\begingroup\$ @aditsu Thanks! 9999 hmmm, looks like it'll take a couple of days, well back to the drawing board -_- \$\endgroup\$
    – Rnet
    Oct 17, 2015 at 15:45
  • 1
    \$\begingroup\$ bin(m)[2:] should be shorter than the format string. Double assignment on b=m=1 should save a few as well. \$\endgroup\$
    – primo
    Oct 17, 2015 at 20:50
4
\$\begingroup\$

Pyth, 10 bytes

f<eS`*TQ`2

Run the code.

A port of my Python answer, taking from Maltysen the use of f to find the first positive number that meets a condition.

\$\endgroup\$
4
\$\begingroup\$

PHP, 50 bytes

while(preg_match('/[^01]/',$argv[1]*++$y));echo$y;

Some test cases

1 > 1
2 > 5
12 > 925
21 > 481
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Was gonna make something like this, this is even a tad shorter than I had in mind \$\endgroup\$
    – Martijn
    Oct 19, 2015 at 9:22
4
\$\begingroup\$

CJam, 19 17 16 bytes

li:V!{)_V*sAs-}g

Try it online

Brute force solution, trying values sequentially until one meeting the condition is found.

The latest version saves 2 bytes thanks to using As instead of "01" to build a string containing 0 and 1, as suggested by @aditsu. The full proposed solution in the comment saves another byte, but it looks fairly different from mine, so I didn't want to post it under my name.

And 1 more byte saved by @Dennis.

Explanation:

li      Get input and convert to int.
:V      Save it in variable V.
!       Negate the value. Since we saved it in V, we don't need it on the stack anymore.
        But we need 0 on the stack as the start value for y. This conveniently
        accomplishes both with a single operator, since the input is guaranteed to be
        larger than 0.
{       Loop over y.
  )       Increment y.
  _       Copy it.
  V*      Multiply with input in variable V.
  s       Convert to string.
  As      Push the string "10", as the number 10 converted to a string .
  -       Remove 0 and 1 digits. This will result in an empty list if there were only
          0 and 1 digits. The empty list is falsy, and will terminate the loop.
}g      End loop.
\$\endgroup\$
3
  • 3
    \$\begingroup\$ 16: li0{1$+_sAs-}g\/ \$\endgroup\$ Oct 16, 2015 at 12:46
  • \$\begingroup\$ Thanks, @aditsu. I didn't really want to copy your full solution under my name. I did take the As to build the string, since it's a very local change, which in hindsight (which is always much easier...) I should have thought of. \$\endgroup\$ Oct 17, 2015 at 3:05
  • 1
    \$\begingroup\$ @RetoKoradi 16 bytes, less modifications: li:V!{)_V*sAs-}g Also, 0{)_easi*sAs-}g (15 bytes) works with the Java interpreter and command-line arguments. \$\endgroup\$
    – Dennis
    Oct 17, 2015 at 3:15
4
\$\begingroup\$

Java, 213 bytes

import java.math.*;class P{public static void main(String[]a){BigInteger b=new java.util.Scanner(System.in).nextBigInteger(),c,d=c=b.ONE;while(!(b.multiply(c)+"").matches("[01]+"))c=c.add(d);System.out.print(c);}}

Uses BigIntegers and as such has (for all reasonable intents and purposes) unbounded input size. Not sure about the complexity though, that depends on the growth rate of our function here.

Thanks to geobits and ypnypn for saving a handful of bytes.

\$\endgroup\$
6
  • \$\begingroup\$ Hi, how would you call this in your main method please? Trying it but not succeeding \$\endgroup\$ Oct 16, 2015 at 0:38
  • \$\begingroup\$ You'd have to add the static modifier to the method. \$\endgroup\$ Oct 16, 2015 at 2:00
  • 1
    \$\begingroup\$ The question says that the solution should be a complete program, not just a function. \$\endgroup\$
    – raznagul
    Oct 16, 2015 at 13:01
  • \$\begingroup\$ You can cut 15 with b.ONE and !(b.multiply(c)+"") (instead of toString()). \$\endgroup\$
    – Geobits
    Oct 16, 2015 at 16:08
  • \$\begingroup\$ @raznagul: Fixed. \$\endgroup\$ Oct 16, 2015 at 19:33
4
\$\begingroup\$

C++11, many bytes, very fast, wow (1.5 s on 1999999998, 0.2 s on 1…10000)

(Golfed Python version below.)

We start with a concept somewhat similar to aditsu’s solution, where we inductively build up a collection of modular remainders reachable in n steps. But instead of waiting until we find remainder 0, we check for two found remainders a and b such that a·10^n + b = 0. This meet-in-the-middle approach halves the depth of the search tree, so it’s much faster on large inputs and uses much less memory.

Some benchmarks:

$ echo 99999999 | \time ./decbin
1111111122222222333333334444444455555555666666667777777788888889
0.18user 0.01system 0:00.20elapsed 99%CPU (0avgtext+0avgdata 69360maxresident)k
0inputs+0outputs (0major+16276minor)pagefaults 0swaps
$ echo 999999999 | \time ./decbin
111111111222222222333333333444444444555555555666666666777777777888888889
1.22user 0.04system 0:01.27elapsed 100%CPU (0avgtext+0avgdata 434776maxresident)k
0inputs+0outputs (0major+37308minor)pagefaults 0swaps
$ echo 2147483647 | \time ./decbin
4661316525084584315813
0.00user 0.00system 0:00.01elapsed 72%CPU (0avgtext+0avgdata 5960maxresident)k
0inputs+0outputs (0major+1084minor)pagefaults 0swaps
$ echo 1999999998 | \time ./decbin
555555556111111111666666667222222222777777778333333333888888889444444445
1.42user 0.08system 0:01.50elapsed 100%CPU (0avgtext+0avgdata 544140maxresident)k
0inputs+0outputs (0major+38379minor)pagefaults 0swaps
$ \time ./decbin 10000.out
0.19user 0.00system 0:00.20elapsed 100%CPU (0avgtext+0avgdata 3324maxresident)k
0inputs+264outputs (0major+160minor)pagefaults 0swaps

Code:

#include <algorithm>
#include <boost/iterator/transform_iterator.hpp>
#include <fstream>
#include <list>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace boost;
using namespace std;

static inline bool cmp_first_partnered(pair<int, pair<int, int>> a,
                                       pair<int, pair<int, int>> b) {
  return a.first < b.first;
}
static inline bool eq_first_partnered(pair<int, pair<int, int>> a,
                                      pair<int, pair<int, int>> b) {
  return a.first == b.first;
}

static pair<int, int> retrace(int modulus, int place, pair<int, int> state,
                              list<vector<int>>::iterator i,
                              list<vector<int>>::iterator j, string &ret) {
  if (i == j)
    return state;
  state = retrace(modulus, (place * 10LL) % modulus, state, next(i), j, ret);
  int remainder = state.first;
  long long k = state.second * 10LL;
  if (!binary_search(i->cbegin(), i->cend(), remainder)) {
    remainder = ((long long)remainder + modulus - place) % modulus;
    k += 1;
  }
  int digit = k / modulus;
  if (digit != 0 || ret.size())
    ret += '0' + digit;
  return make_pair(remainder, k % modulus);
}

static void mult(int modulus, int x, int y,
                 vector<pair<int, pair<int, int>>>::iterator i,
                 vector<pair<int, pair<int, int>>>::iterator j) {
  if (y - x == 1) {
    for (auto k = i; k != j; k++)
      k->first = (k->first * 10LL) % modulus;
    return;
  }

  int z = (x + y) / 2;
  vector<pair<int, pair<int, int>>>::iterator k = lower_bound(
      i, j, make_pair(int(((long long)modulus * z + 9) / 10), make_pair(0, 0)));
  mult(modulus, x, z, i, k);
  mult(modulus, z, y, k, j);
  inplace_merge(i, k, j,
                [](pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
                  return make_pair(a.first, a.second.second) <
                         make_pair(b.first, b.second.second);
                });
}

static string go(int modulus) {
  if (modulus == 1)
    return "1";

  int sequence = 1;
  list<vector<int>> v = {{0}};
  vector<pair<int, pair<int, int>>> partnered;
  int place = 1;
  while (true) {
    v.emplace_back(v.rbegin()->size() * 2);
    vector<int> &previous = *next(v.rbegin()), &current = *v.rbegin();

    auto offset = [modulus, place, sequence](int a) {
      return (a + (long long)place) % modulus;
    };
    auto old_mid =
        lower_bound(previous.cbegin(), previous.cend(), modulus - place),
         new_mid = lower_bound(previous.cbegin(), previous.cend(), place);
    current.resize(
        set_union(new_mid, previous.cend(),
                  make_transform_iterator(previous.cbegin(), offset),
                  make_transform_iterator(old_mid, offset),
                  set_union(previous.cbegin(), new_mid,
                            make_transform_iterator(old_mid, offset),
                            make_transform_iterator(previous.cend(), offset),
                            current.begin())) -
        current.begin());

    int place2 = modulus - (long long)place * place % modulus;
    auto offset_partnered = [modulus, place, place2,
                             sequence](pair<int, pair<int, int>> a) {
      return make_pair((a.first + (long long)place2) % modulus,
                       make_pair((a.second.first + (long long)place) % modulus,
                                 sequence + a.second.second));
    };
    auto old_mid_partnered =
        lower_bound(partnered.cbegin(), partnered.cend(),
                    make_pair(modulus - place2, make_pair(0, 0))),
         new_mid_partnered = lower_bound(partnered.cbegin(), partnered.cend(),
                                         make_pair(place2, make_pair(0, 0)));
    vector<pair<int, pair<int, int>>> next_partnered(partnered.size() * 2 + 1);
    auto i =
        set_union(partnered.cbegin(), new_mid_partnered,
                  make_transform_iterator(old_mid_partnered, offset_partnered),
                  make_transform_iterator(partnered.cend(), offset_partnered),
                  next_partnered.begin(), cmp_first_partnered);
    if (new_mid_partnered == partnered.cend() ||
        new_mid_partnered->first != place2)
      *i++ = make_pair(place2, make_pair(place, sequence));
    next_partnered.resize(
        set_union(new_mid_partnered, partnered.cend(),
                  make_transform_iterator(partnered.cbegin(), offset_partnered),
                  make_transform_iterator(old_mid_partnered, offset_partnered),
                  i, cmp_first_partnered) -
        next_partnered.begin());
    partnered.swap(next_partnered);

    sequence += previous.size();

    place = (place * 10LL) % modulus;

    mult(modulus, 0, 10, partnered.begin(), partnered.end());
    partnered.resize(
        unique(partnered.begin(), partnered.end(), eq_first_partnered) -
        partnered.begin());

    auto with_first = [](int a) { return make_pair(a, make_pair(a, 0)); };

    vector<pair<int, pair<int, int>>> hits;
    set_intersection(partnered.cbegin(), partnered.cend(),
                     make_transform_iterator(current.cbegin(), with_first),
                     make_transform_iterator(current.cend(), with_first),
                     back_inserter(hits), cmp_first_partnered);

    if (hits.size()) {
      pair<int, pair<int, int>> best = *min_element(
          hits.begin(), hits.end(),
          [](pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
            return a.second.second < b.second.second;
          });
      string ret = "";
      pair<int, int> state =
          retrace(modulus, 1, make_pair(best.second.first, 0), v.begin(),
                  prev(v.end()), ret);
      retrace(modulus, 1, make_pair(best.first, state.second), v.begin(),
              prev(v.end()), ret);
      return ret;
    }
  }
}

int main(int argc, const char *argv[]) {
  ios_base::sync_with_stdio(false);
  if (argc >= 2) {
    ofstream ofs(argv[1]);
    for (int modulus = 1; modulus <= 10000; modulus++)
      ofs << go(modulus) << '\n';
  } else {
    int modulus;
    cin >> modulus;
    cout << go(modulus) << '\n';
  }
  return 0;
}

Python, 280 bytes (8.6 seconds on 1999999998 with PyPy)

n=input()
if n<2:print 1;exit()
d={0:0}
l=[]
k=1
b=x=y=0
while 1:
 for a in[0]+l:
  m=(a+k)%n
  if m not in d:l.append(m);d[m]=b
 k=(k*10)%n;b+=1
 for a in l:
  if(-k*a)%n in d:
   while(a-x)%n:x+=10**d[(a-x)%n]
   while(-y-k*a)%n:y+=10**d[(-y-k*a)%n]
   print(10**b*x+y)/n;exit()
\$\endgroup\$
3
  • 2
    \$\begingroup\$ I understand that you're after the bounty, but even so this is a code-golf question, and the site rules require you to make some effort to golf your code. \$\endgroup\$ Oct 22, 2015 at 18:05
  • 1
    \$\begingroup\$ @PeterTaylor, very well, I added a golfed version in Python. \$\endgroup\$ Oct 25, 2015 at 21:16
  • \$\begingroup\$ 1648 bytes \$\endgroup\$
    – ceilingcat
    Nov 13, 2023 at 7:03
3
\$\begingroup\$

Mathematica 115 bytes

p=Drop[Union[FromDigits/@Flatten[Table[Tuples[{0,1},{k}],{k,2,12}],1]],2];
i=Input[];FirstCase[p,x_/;Divisible[x,i]]
\$\endgroup\$
3
\$\begingroup\$

R, 45 bytes

x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y

Usage:

> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 2
2: 
Read 1 item
[1] 5
> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 21
2: 
Read 1 item
[1] 481
> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 42
2: 
Read 1 item
[1] 2405
\$\endgroup\$
3
\$\begingroup\$

Java 156 bytes

public class P{public static void main(String[]a){long x=Long.valueOf(a[0]),y;for(y=2;!(""+x*y).replaceAll("1|0","").isEmpty();y++);System.out.println(y);}}

Massive thanks to aditsu :)

\$\endgroup\$
5
  • \$\begingroup\$ You don't need a space after [], y can be long too, you forgot the x*y+"" trick in the 2nd program, use isEmpty instead of checking the length, use ; instead of {} \$\endgroup\$ Oct 27, 2015 at 11:04
  • \$\begingroup\$ Anyway, welcome to code golf :) \$\endgroup\$ Oct 27, 2015 at 11:06
  • \$\begingroup\$ I must say, I am impressed, but making y long wouldn't make the code shorter \$\endgroup\$
    – Joba
    Oct 27, 2015 at 12:00
  • \$\begingroup\$ Yes it would: long x=…,y; \$\endgroup\$ Oct 27, 2015 at 12:15
  • \$\begingroup\$ y must start from 1, you can initialize it in the declaration, your class doesn't need to be public, and you can move y++ to the x*y part (x*y++) \$\endgroup\$ Oct 28, 2015 at 9:19
2
\$\begingroup\$

Pyth - 12 11 bytes

Uses filter with numeric arg to get first natural number that fulfills predicate, default is 1 which is what we want. Setwise diff to check if only zeros and ones.

f!-j*QT10U2

Test Suite.

\$\endgroup\$
1
  • \$\begingroup\$ Convert to string and remove "01. Saves one char. \$\endgroup\$
    – Jakube
    Oct 16, 2015 at 4:08
2
\$\begingroup\$

Java, 198 193 181 bytes

Thanks to @aditsu for shaving off 5 bytes AND increasing the range of testable numbers!

Note that some values loop negatively due to how Java parses integers. This could be circumvented by BigInteger, but the bonus was simply less valuable.

I know that I'm not going to win, but I hope this inspires other, shorter, answers.

class A{public static void main(String[] a){for(long i=1;;i++){try{long b=Long.parseLong(a[0]);if(b*i<0)break;Long.parseLong(b*i+"",2);System.out.println(i);}catch(Exception e){}}}}

Ungofled:

class A {
   public static void main(String[] a){
      for(long i=1;;i++){ // infinite loop starting at 1
         try{ // if an error is thrown by attempting to parse as binary, restart while adding 1 to i
            long b=Long.parseLong(a[0]); // For later - it was shorter to declare than use twice
            if(b*i<0)break; // Break out of the program if we have looped.
            Long.parseLong(b*i+"",2); // Multiply out and see if it's passable as a binary number, otherwise, throw error and go back to the top of the loop
            System.out.println(b); // print it out
         } catch (Exception e) {} // do nothing on catch
      }
   }
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ It's funny that Long is shorter than Integer :) \$\endgroup\$
    – anatolyg
    Oct 16, 2015 at 17:16
  • 3
    \$\begingroup\$ The most literal irony there is. \$\endgroup\$ Oct 16, 2015 at 17:58
2
\$\begingroup\$

C, 107 101 bytes (105 99 bytes for 32-bits)

There is a distinct lack of answers in C on code golf. Indeed, C is not the best choice for writing the smallest possible program, but it's not that bad:

main(d,b){char s[9];gets(s);for(b=atoi(s);sprintf(s,"%d",b*d),strspn(s,"01")[s];d++);printf("%d",d);}

You can do without the #includes, but then all the function definitions will be implicit. The main drawback is that this causes the assumption that all functions return ints. This is a problem on 64-bit machines for functions that actually return a pointer. If you are on a 32-bit machine, 2 bytes can be shaved off the above solution:

main(d,b){char s[9];for(b=atoi(gets(s));sprintf(s,"%d",b*d),strspn(s,"01")[s];d++);printf("%d",d);}

Somewhat more readable version:

int main()
{
  char s[9];
  gets(s);
  int d = 1;
  int b = atoi(s);
  for (; sprintf(s, "%d", b * d), strspn(s, "01")[s]; d++);
  printf("%d", d);
}
\$\endgroup\$
2
\$\begingroup\$

C# time near 5 seconds (1 to 10000)

As requested, here is a golfed C# program answering the original challenge. Input as command line argument, output to console.

using System;using System.Collections.Generic;using System.Numerics;using System.Linq;
class P{static void Main(string[] a){int m,n=int.Parse(a[0]);var d=new Dictionary<int,long>();long b;int h;
for(d[n]=0,b=h=1;;b*=2,h=(h*10)%n)foreach(int k in d.Keys.Reverse())if(!d.ContainsKey(m=(h+k)%n)){
var w=d[k]|b;if(m==0){Console.Write(BigInteger.Parse(Convert.ToString(w,2))/n);return;}d.Add(m,w);}}}

Then, as for the bounty: the bounty should go to aditsu, as I think his algorithm cannot be beaten in terms of perfomance. But anatolyg self-answer is amazing too.

Here is my fast implementation in C#. I suppose that in C++ it could be faster (maybe 2x). Compiled and tested with Visual Studio 2010, .NET framework 4, 64 bits, redirecting output to nul. Time : 00:00:05.2604315

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Diagnostics;

class Program
{
   static BigInteger Find(int n)
   {
      var d = new Dictionary<int, long>();
      long kb;
      int km;
      d[n] = 0;
      for (kb = km = 1; ; kb *= 2, km = (km * 10) % n)
      {
         foreach (int key in d.Keys.Reverse())
         {
            int m = (km + key) % n;
            if (!d.ContainsKey(m))
            {
               long w = d[key] | kb;
               if (m == 0)
               {
                  return BigInteger.Parse(Convert.ToString(w, 2));
               }
               d.Add(m, w);
            }
         }
      }
   }

   static void Exec(int n, out string sq, out string sa)
   {
      var v = Find(n);
      sq = (v/n).ToString();
      sa = v.ToString();
   }  

   static void Main(string[] args)
   {
      // string n = Console.ReadLine();
      int limit = int.Parse(args[0]);
      string q ="", a = "";
      Stopwatch x = new Stopwatch();
      x.Start();
      for (int n = 1; n <= limit; n++)
      {
         Exec(n, out q, out a);
         Console.WriteLine("{0} {1} {2}", n, q, a);
      }
      x.Stop();
      Console.Error.WriteLine("{0}", x.Elapsed);
   }
}
\$\endgroup\$
6
  • \$\begingroup\$ Times 4.1s. I misspoke in the bounty. With the latest version of PyPy, aditsu's faster version times approximately 8s, so this is twice as fast. \$\endgroup\$
    – primo
    Oct 20, 2015 at 19:20
  • \$\begingroup\$ I understand that you're after the bounty, but even so this is a code-golf question, and the site rules require you to make some effort to golf your code. \$\endgroup\$ Oct 22, 2015 at 18:07
  • \$\begingroup\$ I'm not after the bounty, it's just an example of implementation. But you're right, I'll add a golfed version. \$\endgroup\$
    – edc65
    Oct 22, 2015 at 18:36
  • \$\begingroup\$ @PeterTaylor could it go now? \$\endgroup\$
    – edc65
    Oct 22, 2015 at 19:01
  • \$\begingroup\$ By the way, why Keys.Reverse? Is the order important? If it's just to avoid concurrency issues, ToList is shorter. \$\endgroup\$ Oct 23, 2015 at 11:10
2
\$\begingroup\$

C with GMP (621 bytes, fast)

I've tried to be fast and short, but favoured fast. This implementation uses a slightly improved version of the number-theoretic speedup I mentioned in a comment on aditsu's answer.

Save as pseudobinary.c and compile with gcc pseudobinary.c -lgmp -o pseudobinary. Note that this allocates so much memory for large inputs that you will need to compile it for a 64-bit platform.

#include <gmp.h>
int main(int y,char*z[]){int i,n,b,c,e,f,m,*j,*k,*l,*r,*h;char *d,*s;mpz_t
B,I,Q;i=atoi(z[1]);n=i;for(b=0;n%10<1;++b)n/=10;for(;n%2<1;++b)n/=2;for(;n%5<1;++b)n/=5;if(n<2)--b;d=calloc(n,1);j=calloc(n,sizeof(int));r=calloc(99,sizeof(int));c=2;d[1]=1;*j=r[1]=e=1;l=j+1;for(s=0;!s;++c){r[c]=e=e*10%n;k=l;for(h=j;h<k;h++){f=*h;m=(e+f)%n;if(d[m]<1){*l++=m;if(m<1){s=malloc(99);memset(s,48,99);for(f=c;f;f=d[m=(m+n-r[f])%n])s[c-f]++;s[c]=0;h=k;}d[m]=c;}}}f=strlen(s);s[f]=48;s[f+b]=0;mpz_init_set_str(B,s,10);mpz_init_set_si(I,i);mpz_init(Q);mpz_divexact(Q,B,I);d=mpz_get_str(0,10,Q);printf("%s\n",d);return 0;}

Loop version for timing (751 bytes)

#include <gmp.h>
char **v;int main(){int i,n,b,c,e,f,m,*j,*k,*l,*r,*h;char *d,*s;mpz_t
B,I,Q;v=calloc(10001,sizeof(char*));v[1]=s=malloc(99);memset(s,48,99);*s=49;s[1]=0;for(i=0;++i<10001;){n=i;for(b=0;n%10<1;++b)n/=10;for(;n%2<1;++b)n/=2;for(;n%5<1;++b)n/=5;d=calloc(n,1);j=calloc(n,sizeof(int));r=calloc(99,sizeof(int));c=2;d[1]=1;*j=r[1]=e=1;l=j+1;for(;!v[n];++c){r[c]=e=e*10%n;k=l;for(h=j;h<k;h++){f=*h;m=(e+f)%n;if(d[m]<1){*l++=m;if(m<1){v[n]=s=malloc(99);memset(s,48,99);for(f=c;f;f=d[m=(m+n-r[f])%n])s[c-f]++;s[c]=0;h=k;}d[m]=c;}}}free(d);free(j);free(r);s=v[n];f=strlen(s);s[f]=48;s[f+b]=0;mpz_init_set_str(B,s,10);mpz_init_set_si(I,i);mpz_init(Q);mpz_divexact(Q,B,I);d=mpz_get_str(0,10,Q);printf("%s\n",d);free(d);s[f+b]=48;s[f]=0;}return 0;}

Ungolfed loop version

#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char **cache;

int main() {
    int i,n,shift,_kb,km,key,m,*ks,*ksi,*nksi,*res,*ii;
    char *d,*s;
    mpz_t B,I,Q;

    cache = calloc(10001,sizeof(char*));
    if (!cache) { printf("Failed to malloc cache\n"); return 1; }
    cache[1]=s = malloc(99);
    memset(s,48,99);
    *s=49;
    s[1]=0;
    for (i=0;++i<10001;) {
        n=i;
        for(shift=0;n%10<1;++shift)n/=10;
        for(;n%2<1;++shift)n/=2;
        for(;n%5<1;++shift)n/=5;

        d = calloc(n,1);
        if (!d) { printf("Failed to malloc d\n"); return 1; }

        ks = calloc(n,sizeof(int));
        if (!ks) { printf("Failed to malloc ks\n"); return 1; }

        res = calloc(99,sizeof(int));
        if (!res) { printf("Failed to malloc res\n"); return 1; }

        _kb = 2;
        d[1] = 1;
        *ks = res[1] = km = 1;
        nksi = ks + 1;

        for(;!cache[n];++_kb) {
            res[_kb] = km = km*10%n;
            ksi = nksi;
            for (ii = ks; ii < ksi; ii++) {
                key = *ii;
                m = (km + key) % n;
                if (d[m] < 1) {
                    *nksi++ = m;
                    if (m < 1) {
                        cache[n] = s = malloc(99);
                        if (!s) { printf("Failed to malloc s\n"); return 1; }
                        memset(s,48,99);
                        for(key=_kb;key;key = d[m = (m + n - res[key]) % n])s[_kb-key]++;
                        s[_kb]=0;
                        ii = ksi; // break
                    }
                    d[m] = _kb;
                }
            }
        }

        free(d);
        free(ks);
        free(res);

        // Add shift * '0'
        s=cache[n];
        key=strlen(s);
        s[key]=48;
        s[key+shift]=0;

        // convert to big integer, divide, print
        mpz_init_set_str(B,s,10);
        mpz_init_set_si(I,i);
        mpz_init(Q);
        mpz_divexact(Q,B,I);
        d = mpz_get_str(0,10,Q);
        if (!s) { printf("Failed to malloc quotient\n"); return 1; }
        printf("%s\n", d);
        free(d);

        // Remove shift * '0'
        s[key+shift]=48;
        s[key]=0;
    }
    return 0;
}
\$\endgroup\$
0
2
+150
\$\begingroup\$

C + GMP, 669

This is really fast for smallish numbers; it starts to choke when the result has more than 64 digits.

#include<gmp.h>
#define B(x)(int)((x*(long)k)%n);
int*M,*H,P[99],n,x,p,q=2,e=1,k=10,y,f,z;char*E,C[99];int b(int k,int t){int
j=E[k],a=1<<(j-2);if(j<2){C[t]=49;return 1;}x=(int)((k+n-P[j]*(long)H[k]%n)%n);if(x)b(x,t);return a+b(H[k],t-a);}int
main(){scanf("%d",&n);E=calloc(n+1,1);M=calloc(n+1,4);H=malloc(n*4);M[1]=E[1%n]=P[1]=1;while(!E[0]){P[++e]=k;p=q;for(x=0;++x<p;){y=B(M[x])if(E[n-y]){E[0]=e;H[0]=M[x];break;}}if(!E[x=0])while(++x<p){y=B(M[x])for(z=0;z<p;++z){f=y+M[z];if(f>=n)f-=n;if(!E[f]){E[f]=e;H[f]=M[x];M[q++]=f;}}}k=B(k)}memset(C,48,98);C[99]=0;x=b(0,97);mpz_t
m,r;mpz_init(r);mpz_init_set_str(m,C+98-x,10);mpz_fdiv_q_ui(r,m,n);puts(mpz_get_str(C,10,r));}

Version that loops to 10000 (671 bytes):

#include<gmp.h>
#define B(x)(int)((x*(long)k)%n);
#define N 10001
int M[N],H[N],P[99],n=0,x,p,q,e,k,y,f,z;char E[N],C[99];int b(int k,int t){int
j=E[k],a=1<<(j-2);if(j<2){C[t]=49;return 1;}x=(int)((k+n-P[j]*(long)H[k]%n)%n);if(x)b(x,t);return a+b(H[k],t-a);}int
main(){while(++n<N){memset(E,M[0]=0,n);M[1]=E[1%n]=P[1]=e=1;q=2;k=10;while(!E[0]){P[++e]=k;p=q;for(x=0;++x<p;){y=B(M[x])if(E[n-y]){E[0]=e;H[0]=M[x];break;}}if(!E[x=0])while(++x<p){y=B(M[x])for(z=0;z<p;++z){f=y+M[z];if(f>=n)f-=n;if(!E[f]){E[f]=e;H[f]=M[x];M[q++]=f;}}}k=B(k)}memset(C,48,98);C[99]=0;x=b(0,97);mpz_t
m,r;mpz_init(r);mpz_init_set_str(m,C+98-x,10);mpz_fdiv_q_ui(r,m,n);puts(mpz_get_str(C,10,r));}}

Here are some commands for testing my code as well as my competitors', and the results on my laptop:

ls -l *.c*       
-rw-r--r-- 1 aditsu aditsu  669 Oct 27 15:01 mult-aditsu-single.c
-rw-r--r-- 1 aditsu aditsu  671 Oct 27 15:01 mult-aditsu.c
-rw-r--r-- 1 aditsu aditsu 3546 Oct 27 15:01 mult-anatoly.c
-rw-r--r-- 1 aditsu aditsu 6175 Oct 27 15:01 mult-anders.cpp
-rw-r--r-- 1 aditsu aditsu  621 Oct 27 15:01 mult-peter-single.c
-rw-r--r-- 1 aditsu aditsu  751 Oct 27 15:01 mult-peter.c

gcc -w -march=native -O3 mult-aditsu-single.c -lgmp -o mult-aditsu-single
gcc -w -march=native -O3 mult-aditsu.c -lgmp -o mult-aditsu
gcc -w -march=native -O3 mult-peter-single.c -lgmp -o mult-peter-single
gcc -w -march=native -O3 mult-peter.c -lgmp -o mult-peter
gcc -w -march=native -O3 --std=c99 mult-anatoly.c -o mult-anatoly
g++ --std=c++11 -march=native -O3 mult-anders.cpp -o mult-anders

for i in {1..5}; do time ./mult-anders mult-anders.txt; done
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.344 total
./mult-anders mult-anders.txt  0.36s user 0.00s system 99% cpu 0.358 total
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.346 total
./mult-anders mult-anders.txt  0.35s user 0.00s system 99% cpu 0.347 total
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.344 total

for i in {1..5}; do ./mult-anatoly mult-anatoly.txt; done
Time: 0.254416
Time: 0.253555
Time: 0.245734
Time: 0.243129
Time: 0.243345

for i in {1..5}; do time ./mult-peter > mult-peter.txt; done
./mult-peter > mult-peter.txt  0.14s user 0.00s system 99% cpu 0.137 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 97% cpu 0.153 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 99% cpu 0.149 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 99% cpu 0.150 total
./mult-peter > mult-peter.txt  0.14s user 0.00s system 99% cpu 0.138 total

for i in {1..5}; do time ./mult-aditsu > mult-aditsu.txt; done
./mult-aditsu > mult-aditsu.txt  0.06s user 0.00s system 95% cpu 0.058 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 97% cpu 0.055 total
./mult-aditsu > mult-aditsu.txt  0.06s user 0.00s system 99% cpu 0.056 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 99% cpu 0.054 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 98% cpu 0.055 total

md5sum *.txt
6eef8511d3bc5769b5d9218be2e00028  mult-aditsu.txt
6eef8511d3bc5769b5d9218be2e00028  mult-anatoly.txt
6eef8511d3bc5769b5d9218be2e00028  mult-anders.txt
6eef8511d3bc5769b5d9218be2e00028  mult-peter.txt
\$\endgroup\$
4
  • \$\begingroup\$ An answer well-deserving of a bounty. I take particular interest in this problem (and your initial solution), because it is a special case of the subset sum problem, which is known to be NP-complete (given a list of the residues of 10ⁱ mod n, find the earliest subset which sums to n). \$\endgroup\$
    – primo
    Oct 28, 2015 at 11:08
  • \$\begingroup\$ @primo Thank you :) My approach here is different - I double the number of digits at each step rather than just incrementing it, and I also check first (very quickly) if any of the new numbers would be a solution, before actually calculating them. And I'm sure there's still room for golfing. \$\endgroup\$ Oct 28, 2015 at 15:34
  • \$\begingroup\$ Interesting. When I tried doubling the number of digits at each step it ended up being slower. Maybe the pre-check for solutions makes a big difference. \$\endgroup\$ Oct 28, 2015 at 16:38
  • \$\begingroup\$ @PeterTaylor that's possible.. it seems that you're also calling calloc in a loop, which might slow it down. Anyway, I'd like to add an ungolfed version of my code when I find some time, and I also have an idea how to make it faster for bigger/nastier numbers. \$\endgroup\$ Oct 28, 2015 at 17:14
2
\$\begingroup\$

T-SQL, 164 156 155 154 159 bytes

(-1 byte. Thanks Jonathan!)

(-1 more because why do I have trailing spaces on lines? SMH)

(+5 realized my golfing broke things)

create function b(@ int)
returns int
as begin
declare @b varchar(max)='',@i int=@
while @>0SELECT @b=cast(@%2 as varchar)+@b,@/=2
return cast(@b as int)/@i
end

I don't know why I keep coming back to these questions where I'm supposed to convert to Binary... T-SQL doesn't know how to do that right.

In any case, here's a SQLFiddle.

Un-golfed:

create function binarySquare(@id int)
returns int 
as BEGIN

Most of this stuff is required to write a function in T-SQL, as far as I'm aware.

    declare @bin nvarchar(max) = ''

Create a blank string that we're going to store as our binary number.

    declare @id2 int = @id

Save the input value for use at the end. It seems like there should be a way to use the original input even if we change the value, but I can't find one.

    while @id>0
      BEGIN
        SET @bin = cast(@id%2 as varchar(1)) + @bin

So we take our original input, MOD it with 2 to find the remainder, and that's going to be our next smallest digit. For example, 5%2 = 1

        SET @id = @id/2

Then we take our number, and divide it in half. Because it's an int type, it rounds it down to the nearest whole number, so 5/2 = 2. END We then loop through this until the value is 0. So we end up with 5%2 = 1 5/2 = 2 2%2 = 0 2/2 = 1 1%2 = 1 1/2 = 0 which gives us our binary string value of 101.

    declare @binNum int = (SELECT cast(@bin as int))

We take our binary string and convert it back to an int again.

    return @binNum/@id2

We return our binary string int divided by our original value, per the origin of the question.

END
\$\endgroup\$
3
  • \$\begingroup\$ Is the space in @>0 SELECT not omittable? \$\endgroup\$ Sep 22, 2017 at 21:46
  • \$\begingroup\$ Nice catch! I can never remember what spaces are omit-able... \$\endgroup\$
    – phroureo
    Sep 22, 2017 at 21:47
  • \$\begingroup\$ Most of the time you can omit spaces in between literals and variables / keywords, as they cannot begin with a digit. \$\endgroup\$ Sep 22, 2017 at 22:02
2
\$\begingroup\$

Julia, 38 bytes (brute force approach)

~n=(i=0;while"$((i+=1)n)"⊈"01"end;i)

Attempt This Online!

  • -7 bytes (!!) thanks to MarcMush: rewrite with instead of maximum
  • -1 byte thanks to MarcMush: increment i inside the loop evaluation
\$\endgroup\$
1
1
\$\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\$
1
\$\begingroup\$

Ruby, 46 bytes

I should really eliminate the while loop with an alternative loop.

n,k=gets,0;$_="#{n.to_i*k+=1}"while/[^01]/;p k

Edit: Thanks @manatwork for shaving off 1 byte!

Edit2: Thanks @histocraft for the insane 9 bytes!

Edit: Thanks @manatwork again for shaving off 7 bytes!

\$\endgroup\$
8
  • \$\begingroup\$ z!=z[/[01]+/] is shorter. z[/[^01]/] is even more shorter. \$\endgroup\$
    – manatwork
    Oct 16, 2015 at 16:24
  • \$\begingroup\$ @manatwork Thanks! 1 byte less! \$\endgroup\$ Oct 16, 2015 at 16:26
  • 2
    \$\begingroup\$ Single-line while loops tend to be the shortest: z="#{n.to_i*k+=1}"while z[/[^01]/] \$\endgroup\$
    – histocrat
    Oct 16, 2015 at 16:29
  • \$\begingroup\$ @histocrat That's 9 bytes! And I didn't even know that ruby is capable of this. Thanks! \$\endgroup\$ Oct 16, 2015 at 16:32
  • \$\begingroup\$ Interesting that you not changed the test to negated character set neither after was suggested 2nd time. Any reason? \$\endgroup\$
    – manatwork
    Oct 16, 2015 at 16:34
1
\$\begingroup\$

Scala, 114 Bytes

val i=scala.io.StdIn.readInt;Stream.from(1).foreach{x=>if((i*x+"").map{_.asDigit}.max<2){print(x);System.exit(0)}}

Readable version

val i=scala.io.StdIn.readInt
Stream.from(1).foreach{x => 
    if((i*x+"").map{_.asDigit}.max<2) {
        print(x)
        System.exit(0)
    }
}
\$\endgroup\$
1
\$\begingroup\$

gawk4 brute force, 28+2 = 30 bytes

{while(++n*$0~/[2-9]/);}$0=n

Needs to be called with the -M option for using big numbers. Of course this is ridiculously slow, using big numbers slows it down even more, but theoretically the input is not limited, and RAM usage is negligible.

Usage example ( if you got time to waste ;))

echo 27 | awk -M '{while(++n*$0~/[2-9]/);}$0=n'

gawk4 optimized, 69+2 = 71 bytes

{for(;!a[0];NR*=10)for(i in a)a[j=(s=a[i]+NR)%$0]?0:a[j]=s}$0=a[0]/$0

Well, this ended up being a clone of aditsu's answer. After looking at this question I was still figuring out how to code the subset-sum part, when I couldn't resist looking at the other answers here.

In awk array elements have the (strange ?) behaviour that if you compare a non-existing element to something it is somehow initialized as empty before being compared (I'll admit that I'm not quite sure about what is happening there). So after checking !a[0] the for(i in a) loop starts even without initializing a[$0] to 0 as aditsu did.

Of course the -M option has to be used for this too.

Though it is rather fast it is still remarkably slower than Python. For 79992 this takes around 14 seconds on my 2GHz Core2Duo. And I wouldn't say it works for inputs up to 2^31, because in the worst case it has to build an array of big numbers (gawk4 uses GMP for this), which has the size of the input number. As a 'bonus' large arrays are very very slow in awk...

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