Dado um número inteiro N. Qual é o menor número inteiro maior que N que possui apenas 0 ou 1 como dígitos?

Eu tenho um número inteiro N. Eu tenho que encontrar o menor número inteiro maior que N que não contenha nenhum dígito além de 0 ou 1. Por exemplo: Se, N = 12então, a resposta é 100. Eu codifiquei uma abordagem de força bruta em C ++.

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

O problema é que minha abordagem é muito lenta. Eu acredito que existe uma abordagem muito eficiente para resolver isso. Como posso resolver esse problema com eficiência?

1. Incremento N,

2. Começando pela esquerda, digitalize até encontrar um dígito acima de 1. Incremente o número parcial antes dele e zere o resto.

Por exemplo

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

Prova:

O número solicitado deve ser pelo menos N + 1, é por isso que incrementamos. Agora estamos procurando um número maior ou igual.

Vamos chamar o prefixo de dígitos 0/1 iniciais e sufixo o que vem depois. Devemos substituir o primeiro dígito do sufixo por um zero e definir um prefixo maior. O menor prefixo que se encaixa é o prefixo atual mais um. E o menor sufixo que se encaixa é todos os zeros.

Atualizar:

Esqueci de especificar que o prefixo deve ser incrementado como um número binário , caso contrário, dígitos proibidos poderão aparecer.

Outra possibilidade seria a seguinte:

• Você começa com o maior número decimal do tipo "1111111 ... 1111" suportado pelo tipo de dados usado

  O algoritmo assume que a entrada é menor que esse número; caso contrário, você terá que usar outro tipo de dados.

  Exemplo: Ao usar long long, você começa com o número 1111111111111111111.

• Em seguida, processe cada dígito decimal da esquerda para a direita:
  • Tente alterar o dígito de 1 para 0.
  • Se o resultado ainda for maior que sua entrada, faça a alteração (altere o dígito para 0).
  • Caso contrário, o dígito permanece 1.

Exemplo

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

Prova de correção:

Processamos dígito por dígito neste algoritmo. Em cada etapa, existem dígitos cujo valor já é conhecido e dígitos cujos valores ainda não são conhecidos.

Em cada etapa, analisamos o dígito desconhecido mais à esquerda.

Definimos esse dígito para "0" e todos os outros dígitos desconhecidos para "1". Como o dígito a ser sondado é o mais significativo dos dígitos desconhecidos, o número resultante é o maior número possível, sendo esse dígito um "0". Se esse número for menor ou igual à entrada, o dígito que está sendo testado deve ser um "1".

Por outro lado, o número resultante é menor que todos os números possíveis, onde o dígito que está sendo sondado é um "1". Se o número resultante for maior que a entrada, o dígito deverá ser "0".

Isso significa que podemos calcular um dígito em cada etapa.

Código C

(O código C também deve funcionar em 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 ...

Deixe-me sugerir algumas alternativas.

I. Incrementar. Considere uma modificação do método @YvesDaoust.

1. Aumentar N em 1
2. Expanda o resultado com zero inicial
3. Vá do último para o segundo dígito
   (a) se for menor que 2, deixe tudo como está
   (b) caso contrário, defina-o como 0 e aumente
4. Repita as etapas 3a, b

Exemplos:

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

Você obtém resultado no formato decimal.

II Dividindo.

1. Aumentar N em 1
2. Definir soma como 0
3. Divida o resultado por 10 para obter as partes div (D) e mod (M)
4. Marque M
   (a) se M exceder 1 e aumente D
   (b) caso contrário aumente a soma em M * 10 ^k , onde k é o número da iteração atual (começando com 0)
5. Repita as etapas 3,4 até D ser 0

Exemplo 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

Exemplo 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

Exemplo 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

Exemplo 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