Reverse the Digits

Q: Como inverter os dígitos de um número sem convertê-lo em uma cadeia de caracteres?

Repita duas etapas até que o número seja 0 : obtenha o último dígito com n % 10 e acrescente-o ao resultado com result = result * 10 + digit ; em seguida, remova-o com n = n / 10 , usando divisão inteira. Para 1234 , o resultado cresce assim: 4, 43, 432 e 4321.

Q: Qual é a complexidade de tempo para inverter um número inteiro?

O loop é executado uma vez por dígito decimal, e um número n tem cerca de log10(n) + 1 dígitos, então o tempo é O(log n) . A versão aritmética usa espaço extra O(1) ; a versão com string armazena os dígitos como texto, o que é O(log n) .

InicianteMatemática e simulação

+10

Você recebe um número inteiro não negativo n. Retorne o número obtido ao escrever seus dígitos decimais na ordem inversa. Os zeros que ficarem no início são descartados, então 120 se torna 21.

Função

reverseDigits(n: integer) → integer

ninteger: o inteiro não negativo a ser invertido
Retornainteger: os dígitos de n em ordem inversa, como um número

Restrições

0 ≤ n < 10⁹
O número invertido também cabe em um inteiro assinado de 32 bits.

Exemplos

Entrada: n = 1234
Saída: 4321
Explicação: Os dígitos de 1234 são 1, 2, 3 e 4. Lidos do fim, são 4, 3, 2 e 1, que formam 4321.

Entrada: n = 120
Saída: 21
Explicação: Lendo de trás para frente, 120 fornece os dígitos 0, 2 e 1. Um zero à esquerda não conta em um número, então a resposta é 21.

Entrada: n = 0
Saída: 0
Explicação: 0 tem um único dígito, e invertê-lo resulta em 0 novamente.

+13 testes ocultos ao enviar

Para ir além

Se n puder ser qualquer inteiro de 32 bits, seu reverso talvez não caiba. Como você detectaria isso antes que a multiplicação cause um estouro?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Inverter o texto decimal é feito em uma linha na maioria das linguagens, e essa é uma boa primeira resposta. Os entrevistadores geralmente fazem uma pergunta complementar, pedindo o mesmo resultado sem strings. A versão aritmética se baseia em duas operações: n % 10 lê o último dígito e n / 10 (divisão inteira) o remove.

Inverta o texto decimal

Intuição

Os dígitos de um número são exatamente os caracteres de sua representação decimal em texto. Transforme n em texto, inverta os caracteres e converta o texto de volta em um número. 1234 se torna "1234", depois "4321" e, então, 4321.

Os zeros à esquerda se resolvem sozinhos. Inverter 120 resulta no texto "021", e analisá-lo como um número ignora o zero à esquerda e retorna 21.

Um número menor que 10^9 tem no máximo 9 dígitos, e tanto o trabalho quanto o texto extra crescem com o número de dígitos, o que é O(log n).

Algoritmo

Converta n em seu texto decimal.
Inverta os caracteres.
Interprete o texto invertido como um número inteiro e retorne-o.

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

Remova e adicione dígitos usando operações aritméticas

Intuição

Retire os dígitos do final de n um de cada vez e adicione cada um ao final de um novo número. n % 10 é o último dígito de n, e n / 10 com divisão inteira o remove. Para adicionar um dígito d ao final de result, desloque o que está lá uma casa para a esquerda e coloque d na casa das unidades: result * 10 + d.

Para 1234, result passa por 4, 43, 432, 4321, enquanto n passa por 123, 12, 1, 0. O loop para quando n chega a 0, então é executado uma vez por dígito.

Zeros à esquerda nunca aparecem. Para 120, o primeiro dígito retirado é 0, e 0 * 10 + 0 continua sendo 0, então não deixa vestígios. Para n = 0, o loop nunca é executado e a resposta é 0. Apenas dois inteiros são mantidos, então o espaço extra é O(1).

Algoritmo

Defina result = 0.
Enquanto n for maior que 0, calcule o último dígito n % 10.
Defina result = result * 10 + digit.
Remova o dígito com n = n / 10, usando divisão inteira.
Retorne 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

Armadilhas e casos extremos

A maioria dos bugs vem da divisão e do fim do loop.

Usar divisão comum quando você precisa de divisão inteira. Em JavaScript, Python 3 e Lua, n / 10 resulta em 123.4, então n nunca volta a ser um número inteiro e result fica cheio de frações. Use Math.floor, // ou a divisão inteira da sua linguagem.
Escrever o loop como while n >= 10. Ele para antes do último dígito, então 1234 volta como 432.
Retornar o texto invertido sem convertê-lo em número. "021" não é o número 21, e a comparação com a resposta esperada falha.
Formatar um double em R com as.character. Quando n é armazenado como double, ele exibe 100000000 como 1e+08, e o texto invertido é 80+e1. Use format(n, scientific = FALSE).

Perguntas frequentes4

Como inverter os dígitos de um número sem convertê-lo em uma cadeia de caracteres?

Repita duas etapas até que o número seja 0: obtenha o último dígito com n % 10 e acrescente-o ao resultado com result = result * 10 + digit; em seguida, remova-o com n = n / 10, usando divisão inteira. Para 1234, o resultado cresce assim: 4, 43, 432 e 4321.

O que acontece com os zeros à direita quando você inverte um número?

Eles se tornariam zeros à esquerda, que um número não tem, então desaparecem. Inverter 120 resulta em 21, e inverter 100000000 resulta em 1. O loop aritmético os descarta sozinho, porque somar 0 a um resultado vazio o mantém em 0.

Qual é a complexidade de tempo para inverter um número inteiro?

O loop é executado uma vez por dígito decimal, e um número n tem cerca de log10(n) + 1 dígitos, então o tempo é O(log n). A versão aritmética usa espaço extra O(1); a versão com string armazena os dígitos como texto, o que é O(log n).

Inverter um número inteiro pode causar estouro?

Sim, quando a entrada pode ser qualquer inteiro de 32 bits. 1000000009 cabe, mas seu reverso, 9000000001, não. Aqui, n é menor que 10^9, então o reverso tem no máximo 9 dígitos e sempre cabe. Com entradas maiores, verifique result > (INT_MAX - digit) / 10 antes de cada multiplicação.

Python

def reverseDigits(n):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

n = 1234

Esperado