Biorąc pod uwagę liczbę całkowitą N. Jaka jest najmniejsza liczba całkowita większa niż N, która ma tylko 0 lub 1 jako cyfry?

Mam liczbę całkowitą N. Muszę znaleźć najmniejszą liczbę całkowitą większą niż N, która nie zawiera żadnej cyfry innej niż 0 lub 1. Na przykład: Jeśli tak, N = 12to odpowiedź brzmi 100. W C ++ zakodowałem podejście z użyciem siły brutalnej.

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

Problem polega na tym, że moje podejście jest zbyt wolne. Uważam, że istnieje bardzo skuteczne podejście do rozwiązania tego. Jak mogę skutecznie rozwiązać ten problem?

1. Przyrost N,

2. Zaczynając od lewej, skanuj, aż znajdziesz cyfrę powyżej 1. Zwiększ liczbę częściową przed nią i wyzeruj resztę.

Na przykład

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

Dowód:

Wymagana liczba musi wynosić co najmniej N + 1, dlatego zwiększamy. Szukamy teraz liczby większej lub równej.

Nazwijmy prefiks początkowymi cyframi 0/1 i sufiksem, co nastąpi później. Musimy zamienić pierwszą cyfrę sufiksu na zero i ustawić większy prefiks. Najmniejszy przedrostek, który pasuje, to bieżący przedrostek plus jeden. Najmniejszy przyrostek, który pasuje, to wszystkie zera.

Aktualizacja:

Zapomniałem podać, że przedrostek musi być zwiększany jako liczba binarna , w przeciwnym razie mogłyby pojawić się zabronione cyfry.

Inną możliwością byłaby następująca:

• Zaczynasz od największej liczby dziesiętnej typu „1111111 ... 1111” obsługiwanej przez użyty typ danych

  Algorytm zakłada, że ​​dane wejściowe są mniejsze niż ta liczba; w przeciwnym razie będziesz musiał użyć innego typu danych.

  Przykład: Podczas używania long longzaczynasz od numeru 1111111111111111111.

• Następnie przetwarzaj każdą cyfrę dziesiętną od lewej do prawej:
  • Spróbuj zmienić cyfrę z 1 na 0.
  • Jeśli wynik jest nadal większy niż wprowadzony, dokonaj zmiany (zmień cyfrę na 0).
  • W przeciwnym razie cyfra pozostaje 1.

Przykład

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

Dowód poprawności:

W tym algorytmie przetwarzamy cyfra po cyfrze. Na każdym etapie znajdują się cyfry, których wartość jest już znana, i cyfry, których wartości nie są jeszcze znane.

Na każdym kroku badamy najbardziej nieznaną lewą cyfrę.

Ustawiamy tę cyfrę na „0”, a wszystkie inne nieznane cyfry na „1”. Ponieważ cyfra, która ma być sondowana, jest najbardziej znaczącą z nieznanych cyfr, wynikowa liczba jest największą możliwą liczbą, przy czym cyfra ta to „0”. Jeśli liczba ta jest mniejsza lub równa wartości wejściowej, badana cyfra musi być „1”.

Z drugiej strony wynikowa liczba jest mniejsza niż wszystkie możliwe liczby, w których badana cyfra to „1”. Jeśli wynikowa liczba jest większa niż wartość wejściowa, cyfra musi wynosić „0”.

Oznacza to, że możemy obliczyć jedną cyfrę na każdym kroku.

Kod C.

(Kod C powinien również działać w C ++):

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

Pozwól, że zasugeruję kilka alternatyw.

I. Zwiększanie. Rozważ to modyfikację metody @YvesDaoust.

1. Zwiększ N o 1
2. Rozwiń wynik o wiodące zero
3. Przejdź od ostatniej do drugiej cyfry
   (a), jeśli jest mniejsza niż 2, pozostaw wszystko tak, jak jest
   (b) w przeciwnym razie ustaw na 0 i zwiększ poprzedzające
4. Powtórz kroki 3a, b

Przykłady:

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

Otrzymasz wynik w formacie dziesiętnym.

II. Działowy.

1. Zwiększ N o 1
2. Ustaw sumę na 0
3. Podziel wynik przez 10, aby uzyskać części div (D) i mod (M)
4. Sprawdź M
   (a), jeśli M przekracza 1, zwiększ D
   (b), w przeciwnym razie zwiększ sumę o M * 10 ^k , gdzie k jest bieżącą liczbą iteracji (zaczynając od 0)
5. Powtarzaj kroki 3,4, aż D będzie wynosić 0

Przykład 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

Przykład 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

Przykład 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

Przykład 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