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?

Si te encuentras con alguna parte que no entiendes puedes dejarnos un comentario y te responderemos lo mas rápido que podamos.

Solución:

1. Incremento N,

2. Comenzando desde la izquierda, escanee hasta que encuentre un dígito por encima de 1. Incremente el número parcial anterior 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, por eso incrementamos. Ahora buscamos un número mayor o igual.

Llamemos a la prefix los dígitos 0/1 iniciales y sufijo lo que viene después. Debemos reemplazar el primer dígito del sufijo por un cero y establecer un mayor prefix. El mas pequeño prefix que se ajusta es el actual prefix mas uno. Y el sufijo más pequeño que cabe es todo ceros.

---

Actualizar:

Olvidé especificar que el prefix debe ser incrementado como un número binariode lo contrario podrían aparecer dígitos prohibidos.

Otra posibilidad sería la siguiente:

• Comienza con el mayor número decimal del tipo “1111111…1111” admitido por el tipo de datos utilizado

  El algoritmo asume que la entrada es más pequeña que este número; de lo contrario, tendrá que usar otro tipo de datos.

  Ejemplo: Al usar long longempiezas con el número 1111111111111111111.

• Luego procesa 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, haga el cambio (cambie el dígito a 0).
  • De lo contrario, el dígito sigue siendo 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 por 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, probamos 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, siendo ese dígito un “0”. Si este número es menor o igual a la entrada, el dígito que se prueba 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 prueba 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.

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

Permítanme sugerir un par de alternativas.

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

1. Aumentar N en 1
2. Expandir resultado con cero inicial
3. Ir del último al segundo dígito
   
   (a) si es menor que 2, deje todo como está
   
   (b) de lo contrario, configúrelo en 0 y aumente el precedente
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

Obtienes el resultado en formato decimal.

---

II. Divisor.

1. Aumentar N en 1
2. Establecer suma en 0
3. Divida el resultado por 10 para obtener partes div (D) y mod (M)
4. Compruebe M
   
   (a) si M excede 1, entonces aumente D
   
   (b) de lo contrario, aumente la suma en M*10^kdonde 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

valoraciones y comentarios

Si guardas alguna suspicacia y forma de progresar nuestro noticia te proponemos ejecutar una crítica y con deseo lo leeremos.

---

---

Utiliza Nuestro Buscador