Dado un entero N. ¿Cuál es el entero más pequeño mayor que N que solo tiene 0 o 1 como dígitos?

Tengo un número entero N. Tengo que encontrar el número entero más pequeño mayor que N que no contenga ningún dígito que no sea 0 o 1. Por ejemplo: si N = 12entonces la respuesta es 100. He codificado un enfoque de fuerza bruta en 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;
        }
    }
}

El problema es que mi enfoque es demasiado lento. Creo que hay un enfoque muy eficiente para resolver esto. ¿Cómo puedo resolver este problema de manera eficiente?

1. Incremento N,

2. Comenzando desde la izquierda, escanee hasta que encuentre un dígito arriba 1. Incremente el número parcial antes y ponga a cero el resto.

P.ej

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

Prueba:

El número solicitado debe ser al menos N + 1, es por eso que incrementamos. Ahora estamos buscando un número mayor o igual.

Llamemos al prefijo los dígitos iniciales 0/1 y el sufijo que sigue. Debemos reemplazar el primer dígito del sufijo por un cero y establecer un prefijo más grande. El prefijo más pequeño que se ajusta es el prefijo actual más uno. Y el sufijo más pequeño que cabe es todos ceros.

Actualizar:

Olvidé especificar que el prefijo debe incrementarse como un número binario ; de lo contrario, podrían aparecer dígitos prohibidos.

Otra posibilidad sería la siguiente:

• Comienza con el número decimal más grande del tipo "1111111 ... 1111" admitido por el tipo de datos utilizado

  El algoritmo supone que la entrada es menor que este número; de lo contrario, tendrá que usar otro tipo de datos.

  Ejemplo: al usar long long, comienza con el número 1111111111111111111.

• Luego procese cada dígito decimal de izquierda a derecha:
  • Intenta cambiar el dígito de 1 a 0.
  • Si el resultado sigue siendo mayor que su entrada, realice el cambio (cambie el dígito a 0).
  • De lo contrario, el dígito permanece 1.

Ejemplo

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

Prueba de corrección:

Procesamos dígito a dígito en este algoritmo. En cada paso, hay dígitos cuyo valor ya se conoce y dígitos cuyos valores aún no se conocen.

En cada paso, exploramos el dígito desconocido más a la izquierda.

Establecemos ese dígito en "0" y todos los demás dígitos desconocidos en "1". Debido a que el dígito a sondear es el más significativo de los dígitos desconocidos, el número resultante es el número más grande posible con ese dígito siendo un "0". Si este número es menor o igual a la entrada, el dígito que se está probando debe ser un "1".

Por otro lado, el número resultante es más pequeño que todos los números posibles donde el dígito que se está probando es un "1". Si el número resultante es mayor que la entrada, el dígito debe ser "0".

Esto significa que podemos calcular un dígito en cada paso.

Código C

(El código C también debería funcionar en 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 ...

Déjame sugerirte un par de alternativas.

I. Incrementando. Considérelo una modificación del método @YvesDaoust.

1. Aumenta N en 1
2. Ampliar el resultado con cero a la izquierda
3. Pase del último al segundo dígito
   (a) si es menor que 2, luego deje todo como está
   (b) de lo contrario, ajústelo a 0 y aumente
4. Repita los pasos 3a, b

Ejemplos:

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

Obtiene el resultado en formato decimal.

II Divisor.

1. Aumenta N en 1
2. Establecer suma a 0
3. Divida el resultado por 10 para obtener las partes div (D) y mod (M)
4. Marque M
   (a) si M excede 1, luego aumente D
   (b) o aumente la suma en M * 10 ^k , donde k es el número de iteración actual (comenzando con 0)
5. Repita los pasos 3,4 hasta que D sea 0

Ejemplo 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

Ejemplo 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

Ejemplo 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

Ejemplo 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