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 caso de todos 9 toca cada dígito. La versión con salida anticipada se detiene después de los 9 finales y usa O(1) de espacio adicional, 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 contener 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, del más significativo al menos 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.

Para ir más allá

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

Solución

Un número de 100 dígitos desborda cualquier entero de 64 bits, cuyo límite está cerca de 1.8 × 10^19, así que no puedes convertirlo y sumarlo. Súmalo como lo haces en papel, empezando por el último dígito y llevando una cifra. Sumar 1 cambia solo los 9 finales, que se convierten en 0, y el dígito que está a su izquierda.

Sumar con llevada, cifra por cifra

Intuición

Empieza con un acarreo de 1, el que estás sumando. En cada dígito, de derecha a izquierda, el total de la columna es el dígito más el acarreo: total % 10 va a la respuesta y total / 10 es el siguiente acarreo. El total es como máximo 9 + 1 = 10, así que el acarreo es 0 o 1. Un acarreo que queda después del primer dígito se convierte en un nuevo dígito inicial, como en 999 + 1 = 1000.

Produces la respuesta empezando por el último dígito, así que recógela de esa manera y inviértela al final. Eso requiere O(n) 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, del último al 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

Un dígito menor que 9 absorbe un acarreo de 1: aumenta en uno y cada dígito a su izquierda conserva su valor. Solo un 9 transmite el acarreo al convertirse en 0. Así que puedes detenerte en el primer dígito menor que 9 y devolver el arreglo de entrada, modificado en el lugar. Para [2, 9, 0, 9], el último 9 se convierte en 0, el 0 se convierte en 1 y devuelves [2, 9, 1, 0] sin leer los dos primeros dígitos.

Si ningún dígito es menor que 9, el número era 10^n - 1 y la respuesta es un 1 seguido de n ceros. Ese es el único caso que necesita un arreglo nuevo, así que, en los demás casos, el espacio adicional es O(1).

Algoritmo

Recorre los índices desde el último hasta el primero.
Si el dígito es menor que 9, auméntalo en uno y devuelve el arreglo.
De lo contrario, el dígito es 9: establécelo en 0 y avanza un lugar hacia la izquierda.
Si el bucle termina, todos los dígitos eran 9: devuelve 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

Convertir el arreglo en un entero y viceversa. Un entero de 64 bits contiene como máximo 19 o 20 dígitos, así que 100 dígitos provocan un desbordamiento, y un número de punto flotante pierde los últimos dígitos incluso antes.
Olvidar el dígito extra. [9, 9, 9] debe convertirse en [1, 0, 0, 0]; el código que solo reescribe las posiciones existentes devuelve [0, 0, 0].
Sumar 1 al primer dígito. El arreglo está ordenado de mayor a menor importancia, así que el dígito de las unidades es el último elemento.
No retornar cuando un dígito menor que 9 absorbe el acarreo. Entonces, el bucle cambia dígitos que deben permanecer iguales: [1, 9, 3] debe convertirse en [1, 9, 4].
En Lua y R, los arreglos empiezan en 1, así que el último dígito está en el índice n, no en n - 1.

Preguntas frecuentes3

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

Ambos enfoques se ejecutan en tiempo O(n) para n dígitos, porque el caso de todos 9 toca cada dígito. La versión con salida anticipada se detiene después de los 9 finales y usa O(1) de espacio adicional, excepto cuando la respuesta necesita un nuevo dígito inicial.

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

El número puede tener 100 dígitos, y un entero de 64 bits llega hasta aproximadamente 1.8 × 10^19, que tiene 20 dígitos. Python y Ruby tienen enteros ilimitados, así que la conversión funciona allí, pero el código no se puede trasladar a otros lenguajes. Trabajar dígito por dígito nunca provoca un desbordamiento.

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

Usa el método de columnas con un índice al final de cada arreglo. Cada columna suma los dos dígitos, tratando un dígito faltante como 0, más el acarreo. Detente cuando se hayan usado ambos arreglos y el acarreo sea 0; luego invierte los dígitos recopilados.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

digits = [4, 3, 9]

Salida Esperada

[4, 4, 0]