Bei einer ganzen Zahl N. Was ist die kleinste ganze Zahl größer als N, deren Ziffern nur 0 oder 1 enthalten?

Ich habe eine Ganzzahl N. Ich muss die kleinste Ganzzahl größer als N finden, die keine andere Ziffer als 0 oder 1 enthält. Zum Beispiel: Wenn N = 12dann die Antwort lautet 100. Ich habe einen Brute-Force-Ansatz in C ++ codiert.

int main() {
    long long n;
    cin >> n;

    for (long long i = n + 1; ; i++) {
        long long temp = i;
        bool ok = true;
        while (temp != 0) {
            if ( (temp % 10) != 0 && (temp % 10) != 1) {
                ok = false;
                break;
            }
            temp /= 10;
        }
        if (ok == true) {
            cout << i << endl;
            break;
        }
    }
}

Das Problem ist, mein Ansatz ist zu langsam. Ich glaube, es gibt einen sehr effizienten Ansatz, um dies zu lösen. Wie kann ich dieses Problem effizient lösen?

1. Inkrement N,

2. Scannen Sie von links, bis Sie eine Ziffer über 1 finden. Erhöhen Sie die Teilzahl davor und setzen Sie den Rest auf Null.

Z.B

12 -> 13 -> 1|3 -> 10|0
101 -> 102 -> 10|2 -> 11|0
109 -> 110 -> 110|
111 -> 112 -> 11|2 -> 100|0
198 -> 199 -> 1|99 -> 10|00
1098 -> 1099 -> 10|99 -> 11|00
10203 -> 10204 -> 10|204 -> 11|000
111234 -> 111235 -> 111|235 -> 1000|000
...

Beweis:

Die angeforderte Nummer muss mindestens N + 1 sein, deshalb erhöhen wir. Wir suchen jetzt nach einer größeren oder gleichen Zahl.

Nennen wir das Präfix die ersten 0/1-Ziffern und das Suffix, was danach kommt. Wir müssen die erste Ziffer des Suffix durch eine Null ersetzen und ein größeres Präfix setzen. Das kleinste passende Präfix ist das aktuelle Präfix plus eins. Und das kleinste passende Suffix sind alle Nullen.

Aktualisieren:

Ich habe vergessen anzugeben, dass das Präfix als Binärzahl erhöht werden muss, da sonst verbotene Ziffern auftreten können.

Eine andere Möglichkeit wäre die folgende:

• Sie beginnen mit der größten Dezimalzahl des Typs "1111111 ... 1111", die vom verwendeten Datentyp unterstützt wird

  Der Algorithmus geht davon aus, dass die Eingabe kleiner als diese Zahl ist. Andernfalls müssen Sie einen anderen Datentyp verwenden.

  Beispiel: Bei der Verwendung long longbeginnen Sie mit der Nummer 1111111111111111111.

• Verarbeiten Sie dann jede Dezimalstelle von links nach rechts:
  • Versuchen Sie, die Ziffer von 1 auf 0 zu ändern.
  • Wenn das Ergebnis immer noch größer als Ihre Eingabe ist, nehmen Sie die Änderung vor (ändern Sie die Ziffer auf 0).
  • Ansonsten bleibt die Ziffer 1.

Beispiel

Input = 10103
Start:  111111
Step 1: [1]11111, try [0]11111; 011111 > 10103 => 011111 
Step 2: 0[1]1111, try 0[0]1111; 001111 < 10103 => 011111
Step 3: 01[1]111, try 01[0]111; 010111 > 10103 => 010111
Step 4: 010[1]11, try 010[0]11; 010011 < 10103 => 010111
Step 5: 0101[1]1, try 0101[0]1; 010101 < 10103 => 010111
Step 6: 01011[1], try 01011[0]; 010110 > 10103 => 010110
Result: 010110

Korrektheitsnachweis:

Wir verarbeiten in diesem Algorithmus Ziffer für Ziffer. In jedem Schritt gibt es Ziffern, deren Wert bereits bekannt ist, und Ziffern, deren Werte noch nicht bekannt sind.

In jedem Schritt prüfen wir die am weitesten links stehende unbekannte Ziffer.

Wir setzen diese Ziffer auf "0" und alle anderen unbekannten Ziffern auf "1". Da die zu prüfende Ziffer die höchstwertige der unbekannten Ziffern ist, ist die resultierende Zahl die größtmögliche Zahl, wobei diese Ziffer eine "0" ist. Wenn diese Zahl kleiner oder gleich der Eingabe ist, muss die zu prüfende Ziffer eine "1" sein.

Andererseits ist die resultierende Zahl kleiner als alle möglichen Zahlen, bei denen die zu prüfende Ziffer eine "1" ist. Wenn die resultierende Zahl größer als die Eingabe ist, muss die Ziffer "0" sein.

Dies bedeutet, dass wir in jedem Schritt eine Ziffer berechnen können.

C-Code

(Der C-Code sollte auch unter C ++ funktionieren):

long long input;
long long result;
long long digit;

... read in input ...

result = 1111111111111111111ll;
digit = 1000000000000000000ll;

while( digit > 0 )
{
    if(result - digit > input)
    {
        result -= digit;
    }
    digit /= 10;
}

... print out output ...

Lassen Sie mich einige Alternativen vorschlagen.

I. Inkrementieren. Betrachten Sie es als eine Modifikation der @ YvesDaoust-Methode.

1. Erhöhen Sie N um 1
2. Erweitern Sie das Ergebnis mit der führenden Null
3. Gehen Sie von der letzten zur zweiten Ziffer
   (a), wenn sie kleiner als 2 ist, und lassen Sie alles so, wie es ist
   (b), andernfalls setzen Sie es auf 0 und erhöhen Sie es vorher
4. Wiederholen Sie die Schritte 3a, b

Beispiele:

1. N = 0 -> 1 -> (0)|(1) -> 1
2. N = 1 -> 2 -> (0)|(2) -> (1)|(0) -> 10
3. N = 101 -> 102 -> (0)|(1)(0)(2) -> (0)|(1)(1)(0) -> (0)|(1)(1)(0) -> (0)|(1)(1)(0) -> 110
4. N = 298 -> 299 -> (0)|(2)(9)(9) -> (0)|(2)(10)(0) -> (0)|(3)(0)(0) -> (1)|(0)(0)(0) -> 1000

Sie erhalten das Ergebnis im Dezimalformat.

II. Teilen.

1. Erhöhen Sie N um 1
2. Setze die Summe auf 0
3. Teilen Sie das Ergebnis durch 10, um die Teile div (D) und mod (M) zu erhalten
4. Überprüfen Sie M
   (a), wenn M 1 überschreitet, und erhöhen Sie dann D
   (b), andernfalls erhöhen Sie die Summe um M * 10 ^k , wobei k die aktuelle Iterationszahl ist (beginnend mit 0).
5. Wiederholen Sie die Schritte 3,4, bis D 0 ist

Beispiel 1:

1. N = 0 -> N = 1
2. sum = 0
3. 1/10 -> D == 0, M == 1 -> sum = sum + 1*10^0 == 1
4. D == 0 -> sum == 1

Beispiel 2:

1. N = 1 -> N = 2
2. sum = 0
3. 2/10 -> D == 0, M == 2 -> D = D + 1 == 1
4. 1/10 -> D == 0, M == 1 -> sum = sum + 1*10^1 == 10
5. D == 0, sum == 10

Beispiel 3:

1. N = 101 -> N = 102
2. sum = 0
3. 102/10 -> D == 10, M == 2 -> D = D + 1 == 11
4. 11/10 -> D == 1, M == 1 -> sum = sum + 1*10^1 = 10
5. 1/10 -> D == 0, M == 1 -> sum = sum + 1*10^2 == 10 + 100 == 110
6. D == 0, sum == 110

Beispiel 4:

1. N = 298 -> N = 299
2. sum = 0
3. 299/10 -> D == 29, M == 9 -> D = D + 1 == 30
4. 30/10 -> D == 3, M == 0 -> sum = sum + 0*10^1 == 0
5. 3/10 -> D == 0, M == 3 -> D = D + 1
6. 1/10 -> D == 0, M == 1 -> sum = sum + 1*10^3 == 1000
7. D == 0, sum == 1000