Plus One

Q: ¿Cuál es la complejidad temporal de Plus One?

Ambos enfoques se ejecutan en tiempo O(n) para n dígitos, porque el peor caso, todos 9, recorre cada dígito. La versión con salida anticipada se detiene después de los 9 finales, así que, para un número que termina en un dígito menor que 9, realiza un paso. Usa espacio adicional O(1) , excepto cuando la respuesta necesita un nuevo dígito inicial.

FácilMatemáticas y simulación

+10

Un número entero no negativo se almacena como un arreglo de sus dígitos decimales, digits, con el dígito más significativo primero: 472 es [4, 7, 2]. Suma uno al número y devuelve los dígitos del resultado en el mismo formato. El número puede tener hasta 100 dígitos, muchos más de los que puede almacenar un entero de 64 bits.

Función

plusOne(digits: integer-array) → integer-array

digitsinteger-array: los dígitos del número, empezando por el más significativo
Devuelveinteger-array: los dígitos del número más uno, empezando por el más significativo

Restricciones

1 ≤ digits.length ≤ 100
0 ≤ digits[i] ≤ 9
digits no tiene ceros iniciales, excepto el propio número 0, que es [0].

Ejemplos

Entrada: digits = [4, 3, 9]
Salida: [4, 4, 0]
Explicación: El número es 439, y 439 + 1 = 440. El último dígito, 9, se convierte en 0 y lleva una unidad al 3, que se convierte en 4.

Entrada: digits = [0]
Salida: [1]
Explicación: El número 0 se escribe como [0], y 0 + 1 = 1.

+13 pruebas ocultas al enviar

Para ir más allá

¿Cómo restarías uno en su lugar, para un número de al menos 1? ¿Qué dígitos cambian y cuándo pierde el resultado su dígito inicial, como en [1, 0, 0]?

Solución

Convertir los dígitos en un número, sumar uno y volver a convertirlo falla aquí: 100 dígitos desbordan cualquier entero de 64 bits, cuyo límite está cerca de 1.8 × 10^19. Así que sumas como lo haces en papel, desde el último dígito y llevando una cifra. La observación que acorta el trabajo: sumar 1 solo cambia los 9 finales, que se convierten en 0, y el primer dígito a su izquierda. Todos los demás dígitos quedan igual.

Sumar llevando, dígito a dígito

Intuición

Escribe el número y suma 1 debajo de su último dígito, como en la escuela. Empieza con un acarreo de 1, el que estás sumando. Para cada dígito, de derecha a izquierda, el total de la columna es el dígito más el acarreo. Su último dígito, total % 10, va en la respuesta, y su dígito de las decenas, total / 10, es el acarreo para la siguiente columna.

Con un acarreo de 1, el total de una columna es como máximo 9 + 1 = 10, así que el acarreo siempre es 0 o 1. Si aún queda un acarreo después del primer dígito, la respuesta gana un nuevo dígito inicial: 999 + 1 necesita una cuarta posición para el 1 de 1000.

La respuesta se obtiene empezando por el último dígito, porque ese es el orden en que la calculas. Recógela en ese orden e inviértela al final. Esto cuesta O(n) de tiempo y un nuevo arreglo de hasta n + 1 dígitos.

Algoritmo

Establece carry en 1 e inicia una lista vacía para la respuesta.
Para cada dígito, desde el último hasta el primero, calcula total = digit + carry.
Añade total % 10 a la respuesta y establece carry en total / 10, redondeado hacia abajo.
Después del bucle, si carry es 1, añádelo.
Invierte la respuesta y devuélvela.

def plusOne(digits):
    result = []  # the answer, last digit first
    carry = 1  # the one you are adding
    for i in range(len(digits) - 1, -1, -1):
        total = digits[i] + carry
        result.append(total % 10)
        carry = total // 10
    if carry > 0:
        result.append(carry)
    result.reverse()
    return result

Detente en el primer dígito menor que 9

Intuición

Observa qué hace el acarreo cuando sumas exactamente 1. Un dígito menor que 9 lo absorbe: 3 se convierte en 4, el acarreo se convierte en 0 y todos los dígitos que están más a la izquierda conservan su valor. Solo un 9 transmite el acarreo al convertirse en 0. Así que sumar 1 significa: convertir los 9 finales en 0 y después sumar 1 al dígito que está justo antes de ellos.

Recorre los dígitos desde el último hacia la izquierda. Si encuentras un 9, escribe 0 y continúa. Si encuentras cualquier otro dígito, auméntalo en uno y devuelve la matriz de inmediato, ya que nada a su izquierda puede cambiar. Para [2, 9, 0, 9], el último 9 se convierte en 0, el 0 se convierte en 1 y te detienes con [2, 9, 1, 0] sin mirar los dos primeros dígitos.

Si el bucle nunca encuentra un dígito menor que 9, todos los dígitos eran 9 y ahora son 0. El número era 10^n - 1, así que la respuesta es un 1 seguido de n ceros. Ese es el único caso que requiere una matriz nueva. En todos los demás casos modificas la entrada en el sitio, así que el espacio adicional es O(1), y el bucle se ejecuta una vez por cada 9 final más un paso adicional.

Algoritmo

Recorre los índices desde el último hasta el primero.
Si el dígito es menor que 9, increméntalo en uno y devuelve el array.
De lo contrario, el dígito es 9: establécelo en 0 y muévete una posición a la izquierda.
Si el bucle termina, todos los dígitos eran 9: devuelve un 1 seguido de los n ceros.

def plusOne(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1  # no carry leaves this digit, so the rest stays as it is
            return digits
        digits[i] = 0  # 9 + 1 = 10: write 0 and carry one to the left
    # Every digit was 9: the answer is 1 followed by zeros.
    return [1] + digits

Errores comunes y casos límite

Las dificultades son el desbordamiento de enteros y el caso en que todos los dígitos son 9.

Convertir el arreglo en un entero y volver a convertirlo. Pasa las pruebas pequeñas, pero falla con los números de 100 dígitos: un entero de 64 bits admite como máximo 19 o 20 dígitos, y un número de punto flotante pierde los últimos dígitos incluso antes.
Olvidar el dígito adicional. [9, 9, 9] debe convertirse en [1, 0, 0, 0], cuatro dígitos. El código que solo reescribe las posiciones existentes devuelve [0, 0, 0].
Sumar 1 al primer dígito en vez de al último. El arreglo está ordenado de mayor a menor significancia, así que el dígito de las unidades está al final.
Olvidar devolver el resultado cuando un dígito menor que 9 absorbe el acarreo. En la versión con salida anticipada, el bucle continúa y cambia dígitos que deben permanecer como están. En [1, 9, 3] solo puede cambiar el 3; la respuesta es [1, 9, 4].
Confundir el orden de los índices en Lua y R, donde los arreglos empiezan en 1: el último dígito está en el índice n, y un nuevo 1 inicial va delante del índice 1.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Plus One?

Ambos enfoques se ejecutan en tiempo O(n) para n dígitos, porque el peor caso, todos 9, recorre cada dígito. La versión con salida anticipada se detiene después de los 9 finales, así que, para un número que termina en un dígito menor que 9, realiza un paso. Usa espacio adicional O(1), excepto cuando la respuesta necesita un nuevo dígito inicial.

¿Por qué no convertir los dígitos en un número entero?

Como el número puede tener 100 dígitos y un entero de 64 bits llega solo hasta aproximadamente 1.8 × 10^19, es decir, 20 dígitos. Python y Ruby tienen enteros ilimitados, así que la conversión funciona en esos lenguajes, pero oculta el objetivo del ejercicio y no se puede trasladar a otros lenguajes. Trabajar dígito por dígito nunca provoca un desbordamiento.

¿Cuándo tiene el resultado más dígitos que la entrada?

Solo cuando todos los dígitos son 9. Entonces, el número es 10^n - 1, y al sumarle uno se obtiene 10^n: un 1 seguido de n ceros. Si algún dígito es menor que 9, absorbe el acarreo, así que la longitud se mantiene igual.

¿Cómo sumas dos números almacenados como arreglos de dígitos?

Usa el método de columnas del primer enfoque con dos índices, uno al final de cada arreglo. Cada columna suma los dos dígitos, considerando que un dígito faltante vale 0, más el acarreo. Continúa hasta que se hayan usado ambos arreglos y el acarreo sea 0; después, invierte los dígitos recopilados.

Python

def plusOne(digits):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

digits = [4, 3, 9]

Esperado

[4, 4, 0]