Ich habe auf der Code Review-Website eine Frage gefunden, die interessant erscheint. Ich denke, OP macht es falsch, kann aber nicht sicher sein ... Also lasst es uns für ihn lösen! (Schreiben Sie ein Programm, keine Funktion / Prozedur)

Eingabe (stdin oder ähnlich):

Eine Ganzzahl xin Dezimalschreibweise. Es ist größer als 1 und kleiner als 2 ^ 31.

Ausgabe (stdout oder ähnlich):

Eine Ganzzahl yin Dezimalschreibweise. Das Produkt x * yin Dezimaldarstellung darf nur die Ziffern 0 und 1 enthalten. Es muss die minimale Zahl größer als 0 sein.

Hinweis: Ausgang nicht begrenzt ist - wenn die minimal yetwa 10 ^ 100, Ihr Programm muss Ausgang alle seine 100 Ziffern (ich weiß nicht , ob es eine vernünftige Grenze ist, wie 2 ^ 64, auf y- lösen hat es nicht ).

Ihr Programm sollte in einer angemessenen Zeit (1 Sekunde? 1 Stunde? - so ähnlich) für alle xin Reichweite beendet sein.

Bonus:

Wenn Ihr Programm keine Begrenzung der Größe der Eingabe (außer RAM) und eine polynomielle Komplexität aufweist, multiplizieren Sie die Byteanzahl Ihres Programms mit 0.8und runden Sie ab.

Beispiel: Eingabe 2; Ausgabe 5, weil 2 * 5 = 10

Beispiel: Eingabe 21; Ausgabe 481, da 21 * 481 = 10101

Haftungsausschluss: Ich bin nicht verantwortlich für die Frage auf der Code Review-Website. Im Falle von Unstimmigkeiten sollte nur die obige Beschreibung als ordnungsgemäße Spezifikation angesehen werden.

OEIS A079339

Pyth, 9 Bytes

f!-`*TQ10

Demonstration

Konvertieren Sie für jedes Multiple in einen String, subtrahieren Sie die Ziffern in 10(in diesem Fall verwenden Sie Pyths handliches int, um str zu verwenden) und negieren Sie das Ergebnis logisch. Beenden Sie die Suche nur, wenn das richtige Multiple gefunden wurde.

Bonuslösung, 10 Bytes:

f.xi`*TQ2Z

Diese Lösung überprüft tatsächlich, ob die Zeichenfolgendarstellung der Zahl als Binärzahl ( i ... 2) behandelt werden kann, und wird beendet, wenn bei diesem Versuch kein Fehler ausgelöst wird.

Python 2, effiziente Lösung, 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

Danke Sp3000 für ein paar Golftipps.

Ich fordere alle anderen auf, (in ihren eigenen Antworten) anzugeben, wie lange es dauert, das Ergebnis für die Eingabe zu erhalten, 72oder 99:) Wenn diese sehr schnell sind, versuchen Sie es mit so etwas wie 79992next (hier noch <1 Sek.).

Erläuterung:

Ich dachte, das wäre nicht nötig (da der Code ziemlich lesbar ist), aber ich habe eine Anfrage bekommen, also hier ist es:

Die erste Idee ist, dass eine binär aussehende Zahl eine Summe von 1 oder mehr verschiedenen Zehnerpotenzen ist. Daher können wir versuchen, verschiedene Zehnerpotenzen auf unterschiedliche Weise zu addieren, bis wir den Rest 0 erhalten.

Wenn wir das naiv machen, ist es dasselbe wie alle binär aussehenden Zahlen zu generieren und sie zu testen. Aber viele Reste werden gleich sein. Eine bessere Möglichkeit besteht darin, nur die kleinste Zahl aufzuzeichnen, die einen bestimmten Rest ergibt, und den von uns aufgezeichneten Zahlen nacheinander größere Potenzen von 10 hinzuzufügen. Das macht das Programm.

dist ein Wörterbuch / eine Karte, in der Schlüssel Reste sind und Werte binär aussehende Zahlen mit diesem Rest sind. Die Initiale n:0ist ein Sonderfall: Es soll sein, 0:0dass wir damit beginnen können, Potenzen hinzuzufügen, aber der Algorithmus stoppt, wenn Schlüssel 0 gefunden wird, also habe ich nstattdessen verwendet, was garantiert den gleichen Effekt hat und die anderen Werte nicht beeinträchtigt.

Dann addieren wir Potenzen von 10 (gespeichert in k) zu allen vorhandenen Zahlen und zeichnen die Reste auf. Wir addieren kzum Rest: (x+k)%nund zur Zahl: d[x]+kund notieren sie nur, wenn es sich um einen neuen Rest handelt: d.setdefault(…)und gehen dann zur nächsten Potenz: k*=10und wiederholen, bis wir den Schlüssel 0 erhalten:while min(d)

Am Ende wird d[0]die binär aussehende Zahl angegeben, die den Rest 0 mod nhat. Wir teilen sie also durch n, um die Lösung zu erhalten.

Hinweis: Das Programm kann effizienter gestaltet werden, indem große Zahlen vermieden werden (Aufzeichnen von Exponenten anstelle von Zehnerpotenzen und Berechnen von Resten von Potenzen aus vorherigen Werten), aber es ist Codegolf, also ...

Tatsächlich habe ich hier eine schnellere Version geschrieben:

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

Python 2, 47 Bytes

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

Verfolgt die eingegebene Nummer nund das aktuelle Vielfache a. Wenn es awie binär aussieht, geben Sie das Verhältnis aus a/n. Um zu überprüfen, ob eine Nummer aus 0's und' s besteht1 ' s besteht, vergleichen wir das maximale Zeichen in seiner Zeichenfolgendarstellung mit '1'.

Verwendet, str(a)anstatt `a`zu vermeiden, dass Sehnsüchte auf enden L. Leider 'L'ist größer als '1'.

Perl, 27 Bytes

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

Zählt man den Shebang als einen, wird die Eingabe von stdin übernommen.

Beispielnutzung

$ 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}{

Eine Verbesserung um zwei Bytes durch @skmrx .

Anstatt gegen einen regulären Ausdruck zu prüfen, wird stattdessen versucht, das Produkt als binäres Literal zu bewerten. Bei einem Fehler wird mit dem nächsten fortgefahren. Typischerweise dieoct Funktion für diesen Zweck verwendet, schneidet jedoch unbemerkt ungültige Ziffern ab, was für diese Herausforderung nicht hilfreich ist.

Perl, 40 Bytes

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

Eine weitaus effizientere Lösung. Wir iterieren über binäre Darstellungen, interpretieren sie als Basis 10 und überprüfen dann die Teilbarkeit. Laufzeiten für alle Werte unter 100 sind vernachlässigbar.

Beispielnutzung

$ echo 72|perl dec-bin.pl
1543209875

$ echo 99|perl dec-bin.pl
1122334455667789

Javascript, 43 Bytes

Dies endete viel kürzer als ich dachte. Es erhöht ysich grundsätzlich um 1 bis y * (input number) = (binary-looking number). Offensichtlich ziemlich ineffizient.

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

Javascript (effizientere Lösung), 53 Bytes

Dieser wird ybinär inkrementiert bis y / (input number) = (number without a remainder). Dann gibt es aus (number without a remainder).

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

Javascript (noch effizientere Lösung), 76 Bytes

Dieser kombiniert beide oben beschriebenen Methoden. Es prüft Inkremente ybis entweder y * (input number) = (binary-looking number)(was bedeutet, dass der Ausgang ist y) ODER y / (input number) = (number without a remainder)(was bedeutet, dass der Ausgang ist (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)

Haskell, 72 70 64 60 58 Bytes

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

Edit: @Jan Dvorak hat mir geholfen, 4 Bytes zu sparen.

Edit: @BlackCap sparte 2 Bytes durch Umschalten auf doNotation. Vielen Dank!

Python 2, 67 65 63 60 Bytes

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

Danke an Status für 2 Bytes und Shebang für 5 Bytes!

JavaScript (ES6) 222 250

Verwenden von Mathematik mit willkürlicher Genauigkeit (Arbeiten mit Zeichenfolgen mit Dezimalstellen)

Dies kann ein wenig mehr golfen werden (erledigt), aber ich mag die Tatsache, dass es nicht auf JS-Standardnummern (17 Dezimalstellen Genauigkeit) beschränkt ist und dass es schnell ist.

Testen Sie das folgende Snippet in einem EcmaScript 6-kompatiblen Browser. Bis zu 9998 ist die Zeit akzeptabel - versuchen Sie es nicht mit 9999 und seien Sie geduldig mit 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>

Mehr lesbar

Dies ist die erste Version mit Modul und langer Division als getrennte Funktionen.

// 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]
}

Perl, 45 Bytes

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

Pyth, 10 Bytes

f<eS`*TQ`2

Führen Sie den Code aus.

Ein Port meine Python Antwort , von der Einnahme Maltysen die Verwendung fdie erste positive Zahl zu finden , das eine Bedingung erfüllt.

PHP, 50 Bytes

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

Einige Testfälle

1 > 1
2 > 5
12 > 925
21 > 481

CJam, 19 17 16 Bytes

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

Probieren Sie es online aus

Brute-Force-Lösung, bei der Werte nacheinander ausprobiert werden, bis eine gefunden wird, die die Bedingung erfüllt.

Die neueste Version speichert 2 Bytes dank Verwendung Asstatt "01"eine Zeichenfolge zu bauen enthält 0und1 , wie von @aditsu vorgeschlagen. Die vollständige vorgeschlagene Lösung im Kommentar speichert ein weiteres Byte, sieht jedoch etwas anders aus als das meine, sodass ich es nicht unter meinem Namen veröffentlichen wollte.

Und 1 weiteres Byte von @Dennis gespeichert.

Erläuterung:

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.

Python 3 2, 101 76 Bytes

-25 Bytes dank @aditsu

fast so effizient wie @ aditsus Lösung

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

Anstatt zu versuchen, die Vielfachen in aufsteigender Reihenfolge durchzugehen, versuche ich, die Produkte durchzugehen, die ich in 'binärer' Form generiere.

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);}}

Verwendet BigInteger s und hat als solches (für alle vernünftigen Absichten und Zwecke) eine unbegrenzte Eingabegröße. Wir sind uns nicht sicher über die Komplexität, die von der Wachstumsrate unserer Funktion hier abhängt.

Dank an Geobits und ypnypn für das Speichern einer Handvoll Bytes.

C 3675 Bytes

So lange für Code Golf ...

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define min_n 1
#define max_n 10000

unsigned *mod_list; // list of mods to check
unsigned mod_list_length; // number of mods to check
char *graph; // for each mod, the power of 10 that gives it

void BuildGraph(unsigned n)
{
    unsigned mod10 = 10 % n;
    int pow = 1;

    memset(graph, 0, n);
    if (n == 1)
        return;
    mod_list[0] = 0; // mod 0 - no path coming to it yet
    mod_list[1] = 1; // mod 1 - 10^0 coming to it
    mod_list_length = 2;
    while (graph[0] == 0)
    {
        // We are going to change mod_list_length by adding new nodes.
        // This should not affect the set of nodes we check, so save its old value.
        unsigned mod_list_limit = mod_list_length;
        for (unsigned i = 0; i < mod_list_limit; ++i)
        {
            unsigned mod = mod_list[i] + mod10;
            if (mod >= n)
                mod -= n;
            if (graph[mod] == 0 && mod != 1) // new node?
            {
                graph[mod] = pow; // record the power of 10 with which we come to this node
                mod_list[mod_list_length++] = mod; // add it to the list of nodes
                if (mod == 0) // found the path to 0?
                    return; // stop calculating
            }
        }
        mod10 = (unsigned long long)mod10 * 10 % n; // go to next power of 10
        ++pow;
    }
}

void PrintPath(unsigned n, char *out)
{
    // Going to output powers of 10 in descending order
    unsigned mod = 0; // start at node 0
    int prev_pow = graph[mod] + 1; // happens to be an acceptable initialization
    do {
        int pow = graph[mod];
        while (--prev_pow > pow) // output the proper number of 0-digits
            *out++ = '0';
        *out++ = '1'; // output the digit 1, corresponding to current power of 10
        if (pow == 0)
            break;
        unsigned mod10 = 1;
        for (int p = 0; p < pow; ++p)
            mod10 = (unsigned long long)mod10 * 10 % n;
        mod = (mod + n - mod10 % n) % n; // go to the preceding node
    } while (mod != 0);
    while (--prev_pow >= 0) // output the proper number of 0-digits
        *out++ = '0';
    *out++ = 0;
}

// The long division algorithm
void DivideAndPrint(char *product, unsigned n, FILE* file)
{
    unsigned long long temp = 0;
    int print = 0;
    while (*product != '\0')
    {
        temp = temp * 10 + *product++ - '0';
        if (temp >= n)
            print = 1;
        if (print)
        {
            unsigned quotient = (unsigned)(temp / n);
            unsigned remainder = temp % n;
            fputc('0' + quotient, file);
            temp = remainder;
        }
    }
    fputc('\n', file);
    assert(temp == 0); // if not divisible, there is a bug somewhere
}

void Calc(unsigned n, FILE* file)
{
    char result[99];
    BuildGraph(n);
    PrintPath(n, result);
    DivideAndPrint(result, n, file);
}

int main(int argc, char* argv[])
{
    unsigned n;

    if (argv[1])
    {
        FILE* file = fopen(argv[1], "wt");
        mod_list = calloc(max_n, sizeof(int));
        graph = calloc(max_n, 1);
        clock_t before = clock();
        for (n = min_n; n <= max_n; ++n)
        {
            Calc(n, file);
        }
        clock_t after = clock();
        fprintf(stderr, "Time: %f\n", (after - before) / (double)CLOCKS_PER_SEC);
    }
    else
    {
        scanf("%u", &n);
        mod_list = calloc(n, sizeof(int));
        graph = calloc(n, 1);
        Calc(n, stdout);
    }
}

Führen Sie das Programm ohne Befehlszeilenparameter nausstdin und gibt das Ergebnis an stdout. Führen Sie mit einem Dateinamen aus - es schreibt die Ergebnisse fürn = 1...10000 in diese Datei und misst die Zeit.

Leistung für 1 ... 10000: 140 ms

Dieser Code verwendet den von aditsu vorgeschlagenen Algorithmus , der aus Geschwindigkeitsgründen in C implementiert ist. Ich habe mich nicht bemüht, Golf zu spielen, damit der Code leichter zu lesen ist.

Ich habe es zuerst in C ++ implementiert std::map, um die Ergebnisse der Suche aufzuzeichnen, und es war ziemlich langsam. Die Tasten von mapsind jedoch aufeinanderfolgende Ganzzahlen (ich nenne sie mods, weil sie Zahlen modulo darstellen n), daher ist es natürlich, ein Array zu verwenden - also habe ich es in C umgeschrieben.

Eine zusätzliche Optimierung betrifft die Werte des Mappings. Um zu vermeiden, dass für jedes Mapping eine große Ganzzahl gespeichert wird mod, speichere ich dort nur die größte Potenz von 10 - es sind gerade genug Informationen, um zum vorherigen zu wechselnmod . Das Array ist also wirklich ein Suchbaum / -graph. Wenn die Suche angekommen ist mod = 0, werden die Potenzen von 10 in absteigender Reihenfolge angegeben, wenn die Knoten des Baums bis zur Wurzel zurückverfolgt werden.

Da die Suche in der Regel ziemlich schnell stoppt und nur ein kleiner Teil der Knoten besucht wird, benötige ich eine Liste der aktiven Knoten. Es ist als Array mod_listmit Länge implementiertmod_list_length .

Einige Laufzeitstatistiken (auf einem Computer mit 16 GB RAM, was für große Computer wichtig zu sein scheint n, da das Programm 5nBytes an Speicher zuweist):

• Eingang 99999999 - 2 Sekunden
• Eingabe 999999999- 27 Sekunden (das Ergebnis ist111111111222222222333333333444444444555555555666666666777777777888888889 - wahrscheinlich das größtmögliche Ergebnis für 32-Bit-Ganzzahlen)
• Eingang 2147483647 - 26 Sekunden (das Ergebnis ist4661316525084584315813 )
• Eingabe 1999999998- 52 Sekunden (wahrscheinlich die längste mögliche Laufzeit für 32-Bit-Ganzzahlen)

C ++ 11, viele Bytes, sehr schnell, wow (1,5 s bei 1999999998, 0,2 s bei 1… 10000)

(Golf-Python-Version unten.)

Wir beginnen mit einem Konzept, das der Lösung von aditsu ähnelt und bei dem wir induktiv eine Sammlung modularer Reste aufbauen, die in n Schritten erreichbar sind. Aber anstatt zu warten, bis wir den Rest 0 gefunden haben, suchen wir nach zwei gefundenen Resten a und b, so dass a · 10 ^ n + b = 0. Dieser Ansatz des Meet-in-the-Middle halbiert die Tiefe des Suchbaums viel schneller bei großen Eingängen und verbraucht viel weniger Speicher.

Einige 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 Sekunden bei 1999999998 mit 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()

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]]

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);}}

Massiver Dank an Aditsu :)

Pyth - 12 11 Bytes

Verwendet Filter mit numerischem Argument, um die erste natürliche Zahl zu erhalten, die das Prädikat erfüllt. Standard ist 1, was wir wollen. Setwise diff, um zu prüfen, ob nur Nullen und Einsen vorhanden sind.

f!-j*QT10U2

Test Suite .

R, 45 Bytes

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

Verwendung:

> 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

Java, 198 193 181 Bytes

Vielen Dank an @aditsu für das Abschneiden von 5 Bytes UND das Erhöhen des Bereichs testbarer Zahlen!

Beachten Sie, dass einige Werte aufgrund der Art und Weise, wie Java Ganzzahlen analysiert, eine negative Schleife bilden. Dies könnte durch BigInteger umgangen werden, aber der Bonus war einfach weniger wertvoll.

Ich weiß, dass ich nicht gewinnen werde, aber ich hoffe, dass dies andere, kürzere Antworten inspiriert.

Klasse 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 (Ausnahme e) {}}}

Ungefled:

Klasse a {
   public static void main (String [] a) {
      for (long i = 1 ;; i ++) {// Endlosschleife ab 1
         try {// Wenn ein Fehler beim Parsen als binär ausgelöst wird, starten Sie neu, während Sie 1 zu i hinzufügen
            long b = Long.parseLong (a [0]); // Für später - es war kürzer zu deklarieren als zweimal zu verwenden
            if (b * i <0) break; // Brechen Sie aus dem Programm aus, wenn wir eine Schleife ausgeführt haben.
            Long.parseLong (b * i + "", 2); // Multipliziere aus und überprüfe, ob es als Binärzahl passierbar ist. Anderenfalls wirf einen Fehler und gehe zurück zum Anfang der Schleife
            System.out.println (b); // Drucke es aus
         } catch (Ausnahme e) {} // mache nichts bei catch
      }
   }
}

C, 107 101 Bytes ( 105 99 Bytes für 32 Bits)

Es gibt einen deutlichen Mangel an Antworten in C auf Code Golf. In der Tat ist C nicht die beste Wahl, um das kleinstmögliche Programm zu schreiben, aber es ist nicht so schlimm:

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);}

Sie können auf das #includes verzichten, aber dann sind alle Funktionsdefinitionen implizit. Der Hauptnachteil ist, dass dies die Annahme hervorruft, dass alle Funktionen ints zurückgeben. Dies ist ein Problem auf 64-Bit-Computern für Funktionen, die tatsächlich einen Zeiger zurückgeben. Wenn Sie sich auf einem 32-Bit-Computer befinden, können mit der obigen Lösung 2 Byte gespart werden:

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

Etwas besser lesbare 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);
}

C # -Zeit nahe 5 Sekunden (1 bis 10000)

Wie gewünscht, finden Sie hier ein Golf-C # -Programm, das die ursprüngliche Herausforderung beantwortet. Eingabe als Kommandozeilenargument, Ausgabe an Konsole.

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);}}}

Dann, was das Kopfgeld betrifft: Das Kopfgeld sollte an Aditsu gehen, da ich denke, dass sein Algorithmus in Bezug auf die Leistung nicht zu übertreffen ist. Aber anatolyg Selbstantwort ist auch erstaunlich.

Hier ist meine schnelle Implementierung in C #. Ich nehme an, dass es in C ++ schneller sein könnte (vielleicht 2x). Kompiliert und getestet mit Visual Studio 2010, .NET Framework 4, 64 Bit, Ausgabe nach nul umleiten. Zeit: 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);
   }
}

C mit GMP (621 Bytes, schnell)

Ich habe versucht, schnell und kurz zu sein, aber schnell bevorzugt. Diese Implementierung verwendet eine leicht verbesserte Version der zahlentheoretischen Beschleunigung, die ich in einem Kommentar zu Aditsus Antwort erwähnt habe .

Speichern unter pseudobinary.cund kompilieren mit gcc pseudobinary.c -lgmp -o pseudobinary. Beachten Sie, dass dadurch so viel Speicher für große Eingaben reserviert wird, dass Sie ihn für eine 64-Bit-Plattform kompilieren müssen.

#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 für das 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;
}

C + GMP, 669

Dies ist sehr schnell für kleinere Zahlen; Es beginnt zu ersticken, wenn das Ergebnis mehr als 64 Stellen hat.

#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, die eine Schleife auf 10000 (671 Byte) durchführt:

#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));}}

Hier sind einige Befehle zum Testen meines Codes sowie der Ergebnisse meiner Konkurrenten auf meinem 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

T-SQL, 164 156 155 154 159 Bytes

(-1 Byte. Danke Jonathan!)

(-1 mehr, weil ich nachgestellte Leerzeichen in Zeilen habe? SMH)

(+5 haben gemerkt, dass mein Golfspiel etwas kaputt gemacht hat)

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

Ich weiß nicht, warum ich immer wieder auf diese Fragen zurückkomme, bei denen ich nach Binary konvertieren soll ... T-SQL weiß nicht, wie man das richtig macht.

In jedem Fall ist hier ein SQLFiddle .

Nicht golfen:

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

Soweit mir bekannt ist, ist das meiste davon erforderlich, um eine Funktion in T-SQL zu schreiben.

    declare @bin nvarchar(max) = ''

Erstellen Sie eine leere Zeichenfolge, die wir als Binärzahl speichern.

    declare @id2 int = @id

Speichern Sie den Eingabewert für die Verwendung am Ende. Es scheint, dass es eine Möglichkeit geben sollte, die ursprüngliche Eingabe zu verwenden, auch wenn wir den Wert ändern, aber ich kann keinen finden.

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

Wir nehmen also unsere ursprüngliche Eingabe, MOD it with 2, um den Rest zu finden, und das wird unsere nächstkleinere Ziffer sein. Zum Beispiel 5% 2 = 1

        SET @id = @id/2

Dann nehmen wir unsere Zahl und teilen sie in zwei Hälften. Da es sich um einen intTyp handelt, wird er auf die nächste ganze Zahl abgerundet, also 5/2 = 2. ENDE Wir durchlaufen diesen dann, bis der Wert 0 ist. Am Ende erhalten wir 5% 2 = 1 5/2 = 2 2 % 2 = 0 2/2 = 1 1% 2 = 1 1/2 = 0, wodurch wir unseren binären String-Wert von 101 erhalten.

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

Wir nehmen unseren Binärstring und konvertieren ihn wieder in einen int.

    return @binNum/@id2

Wir geben unsere Binärzeichenfolge intdividiert durch unseren ursprünglichen Wert nach dem Ursprung der Frage zurück.

END

Ruby, 46 Bytes

Ich sollte die while-Schleife wirklich mit einer alternativen Schleife beseitigen.

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

Edit: Danke @manatwork für das Rasieren von 1 Byte!

Edit2: Danke @histocraft für die verrückten 9 Bytes!

Edit: Nochmals vielen Dank an @manatwork für das Abschneiden von 7 Bytes!

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)}}

Lesbare Version

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

gawk4 Brute Force, 28 + 2 = 30 Bytes

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

Muss mit dem angerufen werden -M Option zur Verwendung großer Nummern werden. Natürlich ist dies lächerlich langsam, wenn große Zahlen verwendet werden, wird es sogar noch langsamer, aber theoretisch ist die Eingabe nicht begrenzt, und die RAM-Auslastung ist vernachlässigbar.

Anwendungsbeispiel (wenn Sie Zeit zum Verschwenden haben ;))

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

gawk4 optimiert, 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

Nun, dies war ein Klon von Aditsus Antwort. Nach dem Anschauen dieser Frage ich mir hatte, überlegte ich immer noch, wie ich den Teil der Teilmengen-Summe codieren sollte, als ich nicht anders konnte, als die anderen Antworten hier zu betrachten.

In awk haben Array-Elemente das (seltsame?) Verhalten, dass, wenn Sie ein nicht vorhandenes Element mit etwas vergleichen, es vor dem Vergleich als leer initialisiert wird (ich gebe zu, dass ich nicht ganz sicher bin, was dort passiert). Nach dem Prüfen startet !a[0]die for(i in a)Schleife also auch ohne Initialisierunga[$0] auf0 wie aditsu tat.

Natürlich die -M Option genutzt werden.

Obwohl es ziemlich schnell ist, ist es immer noch bemerkenswert langsamer als Python. Für 79992diese dauert etwa 14 Sekunden auf meinem 2GHz Core2Duo. Und ich würde nicht sagen, dass es für Eingaben bis zu 2 ^ 31 funktioniert, weil es im schlimmsten Fall ein Array von großen Zahlen erstellen muss (gawk4 verwendet hierfür GMP), das die Größe der Eingabenummer hat. Als "Bonus" sind große Arrays in awk sehr, sehr langsam ...

Dyalog APL , 25

Dies definiert ein richtiges Programm "P" (nicht nur eine unbenannte Funktion):

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

2∘mit 2 als linke Argument beginnen ,
0::wenn es ein Fehler ist ...
⍵∇⍨1+⍺nennen sich mit einem linken Argument erhöht
⍺×⍵mehrfach nach links und rechts Argumente
⍕in String machen
⍎¨machen jedes Zeichen in einer Reihe
~versuchen , nicht logisch (wenn es fehlschlägt, gehen Sie auf die Fehlerbehandlung oben, sonst ...) gibt
⍺⊣das aktuelle linke Argument zurück.

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