Palindrome Number

Q: Um número negativo é um palíndromo?

Não. Lido de trás para frente, -121 se torna 121- , e o sinal de menos não tem um caractere correspondente na outra extremidade. Portanto, todo número inteiro negativo retorna false .

Q: Qual é a complexidade de tempo de Palindrome Number?

As duas abordagens são executadas em tempo O(log x) , porque um número x tem cerca de log10(x) dígitos, e cada um é processado uma vez. A abordagem com string usa espaço extra O(log x) para o texto; a reversão da metade usa O(1) .

FácilMatemática e simulação

+10

Um número é um palíndromo quando seus dígitos são lidos da mesma forma da esquerda para a direita e da direita para a esquerda, como 1221. Dado um número inteiro x, retorne true se ele for um palíndromo e false caso contrário. Um número negativo nunca conta, porque seu sinal de menos não tem um correspondente na outra extremidade.

Função

isPalindrome(x: integer) → boolean

xinteger: o número inteiro a verificar, possivelmente negativo
Retornaboolean: verdadeiro se x for lido da mesma forma nas duas direções, falso caso contrário

Restrições

-2³¹ ≤ x ≤ 2³¹-1
Todo número negativo retorna false.

Exemplos

Entrada: x = 121
Saída: true
Explicação: Lido de trás para frente, 121 ainda é 121, então a resposta é true.

Entrada: x = -121
Saída: false
Explicação: Lido ao contrário, -121 se torna 121-, que é um texto diferente, então a resposta é false.

Para ir além

Você consegue resolver isso sem converter o inteiro em uma string?

Dicas

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

0 de 3 abertas

Solução

Um número é um palíndromo quando é igual ao seu próprio reverso. Como texto, isso exige apenas uma comparação. Sem usar texto, reconstruir o número inteiro na ordem inversa pode causar estouro; por isso, inverta apenas a segunda metade dos dígitos e compare-a com a primeira metade.

Compare a string com sua inversa

Intuição

Escreva o número como texto e compare-o com sua versão invertida. Números negativos não precisam de tratamento especial: -121 começa com um sinal de menos e termina com um dígito, então nunca é igual à sua versão invertida 121-.

O texto tem um caractere por dígito, cerca de log10(x) caracteres e, no máximo, 11 aqui. O custo é a string extra.

Algoritmo

Converta x em uma string s.
Inverta s.
Retorne se s é igual à sua versão invertida.

def isPalindrome(x):
    s = str(x)
    # A minus sign sits only at the front, so a negative never matches its reverse.
    return s == s[::-1]

Inverta metade do número

Intuição

x % 10 fornece o último dígito, e a divisão inteira por 10 o remove. Mover os dígitos do final de x para um segundo número half constrói o inverso dos dígitos removidos. Pare quando half for maior ou igual ao que restou de x: você já pegou metade dos dígitos. 1221 termina com x = 12 e half = 12, um palíndromo. Com uma quantidade ímpar de dígitos, half também contém o dígito do meio: 12321 termina com x = 12 e half = 123, então compare x com half / 10.

Trate dois casos antes do loop. Um número negativo nunca é um palíndromo. Um número que termina em 0 teria que começar com 0, o que só acontece com o próprio 0; sem essa verificação, 10 termina com x = 0 e half = 1, e x == half / 10 é satisfeito por engano. half nunca passa de 6 dígitos, então cabe em qualquer tipo inteiro.

Algoritmo

Se x for negativo ou terminar em 0 e não for 0, retorne false.
Defina half = 0.
Enquanto x > half, defina half = half * 10 + x % 10 e divida x por 10 usando divisão inteira.
Retorne true se x == half (quantidade par de dígitos) ou x == half / 10 (quantidade ímpar de dígitos).

def isPalindrome(x):
    if x < 0:
        return False
    original, reversed_num = x, 0
    while x > 0:
        reversed_num = reversed_num * 10 + x % 10
        x //= 10
    return original == reversed_num

Armadilhas e casos extremos

Esquecer os números negativos. Em linguagens nas quais o resto mantém o sinal, inverter -121 resulta em -121, e a verificação passa. Em Python, onde -1 // 10 é -1, um loop while x != 0 nunca termina.
Não rejeitar números que terminam em 0. A inversão da metade aceita 10. 0 em si é um palíndromo.
Inverter o número inteiro em um inteiro de 32 bits. A inversão de 2147483647 não cabe.
Usar / quando a linguagem divide com frações. Use Math.floor(x / 10) em JavaScript, // em Python, %/% em R e ~/ em Dart.
Comparar a inversão completa com x depois que o loop alterou x. Mantenha uma cópia do valor original.

Perguntas frequentes3

Um número negativo é um palíndromo?

Não. Lido de trás para frente, -121 se torna 121-, e o sinal de menos não tem um caractere correspondente na outra extremidade. Portanto, todo número inteiro negativo retorna false.

Por que inverter apenas metade do número?

Inverter todos os dígitos pode causar estouro em um inteiro de 32 bits: o inverso de 2147483647 é maior que o maior int. Metade dos dígitos sempre cabe, e o loop faz metade do trabalho.

Qual é a complexidade de tempo de Palindrome Number?

As duas abordagens são executadas em tempo O(log x), porque um número x tem cerca de log10(x) dígitos, e cada um é processado uma vez. A abordagem com string usa espaço extra O(log x) para o texto; a reversão da metade usa O(1).

def isPalindrome(x):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

x = 121

Saída Esperada

true