Reverse the Digits

Q: ¿Cómo inviertes los dígitos de un número sin convertirlo en una cadena?

Repite dos pasos hasta que el número sea 0 : toma el último dígito con n % 10 y añádelo al resultado con result = result * 10 + digit ; después, elimínalo con n = n / 10 usando división entera. Para 1234 , el resultado va creciendo así: 4, 43, 432 y 4321.

PrincipianteMatemáticas y simulación

+10

Recibes un entero no negativo n. Devuelve el número que obtienes al escribir sus dígitos decimales en orden inverso. Los ceros que quedan al principio se eliminan, así que 120 se convierte en 21.

Función

reverseDigits(n: integer) → integer

ninteger: el entero no negativo que se debe invertir
Devuelveinteger: los dígitos de n en orden inverso, como un número

Restricciones

0 ≤ n < 10⁹
El número invertido también cabe en un entero de 32 bits con signo.

Ejemplos

Entrada: n = 1234
Salida: 4321
Explicación: Los dígitos de 1234 son 1, 2, 3 y 4. Leídos desde el final, son 4, 3, 2 y 1, que es 4321.

Entrada: n = 120
Salida: 21
Explicación: Leído al revés, 120 da los dígitos 0, 2 y 1. Un cero inicial no cuenta en un número, así que la respuesta es 21.

Entrada: n = 0
Salida: 0
Explicación: 0 tiene un solo dígito, y al invertirlo se obtiene 0 de nuevo.

+13 pruebas ocultas al enviar

Para ir más allá

Si n pudiera ser cualquier entero de 32 bits, es posible que su inverso no cupiera. ¿Cómo detectarías esto antes de que la multiplicación provoque un desbordamiento?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Invertir el texto decimal requiere una línea en la mayoría de los lenguajes, y es una buena primera respuesta. Los entrevistadores suelen preguntar después cómo obtener el mismo resultado sin cadenas. La versión aritmética se basa en dos operaciones: n % 10 lee el último dígito y n / 10 (división entera) lo elimina.

Invierte el texto decimal

Intuición

Los dígitos de un número son exactamente los caracteres de su representación decimal en texto. Convierte n en texto, invierte los caracteres y vuelve a leer el texto como un número. 1234 se convierte en "1234", después en "4321" y, por último, en 4321.

Los ceros iniciales se resuelven solos. Invertir 120 da el texto "021", y al analizarlo como número se ignora el cero inicial y se devuelve 21.

Un número menor que 10^9 tiene como máximo 9 dígitos, y tanto el trabajo como el texto adicional crecen con la cantidad de dígitos, que es O(log n).

Algoritmo

Convierte n en su representación decimal como texto.
Invierte los caracteres.
Analiza el texto invertido como un entero y devuélvelo.

def reverseDigits(n):
    # int() ignores the leading zeros that trailing zeros turn into.
    return int(str(n)[::-1])

Extrae e inserta dígitos mediante operaciones aritméticas

Intuición

Quita los dígitos del final de n de uno en uno y añade cada uno al final de un número nuevo. n % 10 es el último dígito de n, y n / 10 con división entera lo elimina. Para añadir un dígito d al final de result, desplaza lo que hay una posición a la izquierda y coloca d en la posición de las unidades: result * 10 + d.

Para 1234, result pasa por 4, 43, 432, 4321, mientras que n pasa por 123, 12, 1, 0. El bucle se detiene cuando n llega a 0, así que se ejecuta una vez por cada dígito.

Nunca aparecen ceros iniciales. Para 120, el primer dígito que se toma es 0, y 0 * 10 + 0 sigue siendo 0, así que no deja rastro. Para n = 0, el bucle nunca se ejecuta y la respuesta es 0. Solo se conservan dos enteros, así que el espacio adicional es O(1).

Algoritmo

Establece result = 0.
Mientras n sea mayor que 0, calcula el último dígito n % 10.
Establece result = result * 10 + digit.
Elimina el dígito con n = n / 10, usando división entera.
Devuelve result.

def reverseDigits(n):
    result = 0
    while n > 0:
        result = result * 10 + n % 10  # push the last digit of n
        n //= 10                        # drop it from n
    return result

Errores comunes y casos límite

La mayoría de los errores se deben a la división y al final del bucle.

Usar la división ordinaria cuando necesitas división entera. En JavaScript, Python 3 y Lua, n / 10 da 123.4, así que n nunca vuelve a ser un número entero y result se llena de fracciones. Usa Math.floor, // o la división entera de tu lenguaje.
Escribir el bucle como while n >= 10. Se detiene antes del último dígito, así que 1234 da como resultado 432.
Devolver el texto invertido sin analizarlo. "021" no es el número 21, y la comparación con la respuesta esperada falla.
Dar formato a un double en R con as.character. Cuando n se almacena como double, imprime 100000000 como 1e+08, y el texto invertido es 80+e1. Usa format(n, scientific = FALSE).

Preguntas frecuentes4

¿Cómo inviertes los dígitos de un número sin convertirlo en una cadena?

Repite dos pasos hasta que el número sea 0: toma el último dígito con n % 10 y añádelo al resultado con result = result * 10 + digit; después, elimínalo con n = n / 10 usando división entera. Para 1234, el resultado va creciendo así: 4, 43, 432 y 4321.

¿Qué sucede con los ceros finales cuando inviertes un número?

Se convertirían en ceros iniciales, que un número no tiene, así que desaparecen. Invertir 120 da 21, e invertir 100000000 da 1. El bucle aritmético los elimina por sí solo, porque sumar 0 a un resultado vacío lo deja en 0.

¿Cuál es la complejidad temporal de invertir un entero?

El bucle se ejecuta una vez por cada dígito decimal, y un número n tiene aproximadamente log10(n) + 1 dígitos, así que el tiempo es O(log n). La versión aritmética usa espacio adicional O(1); la versión con cadenas almacena los dígitos como texto, lo que ocupa O(log n).

¿Puede la inversión de un entero provocar un desbordamiento?

Sí, cuando la entrada puede ser cualquier entero de 32 bits. 1000000009 cabe, pero su reverso 9000000001 no. Aquí n es menor que 10^9, así que el reverso tiene como máximo 9 dígitos y siempre cabe. Con entradas más grandes, comprueba result > (INT_MAX - digit) / 10 antes de cada multiplicación.

Python

def reverseDigits(n):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

n = 1234

Esperado