LeetCode Easy 9: Palindrome Number em Python

Neste post, o problema 9 do LeetCode, Palindrome Number, é resolvido em Python de quatro formas. O post faz parte da série LeetCode Easy, que traz toda sexta um problema de nível fácil (Easy), da solução mais simples até a mais eficiente. O post anterior tratou do problema 1, o Two Sum. Cada versão tem código comentado e testado, com a análise de complexidade em notação Big O. Os posts ficam reunidos na tag leetcode-easy.

O problema

O Palindrome Number recebe um número inteiro x e pede True se ele for um palíndromo e False se não for. Um palíndromo é lido da mesma forma da esquerda para a direita e da direita para a esquerda.

O 121 é palíndromo. O -121 não é, porque de trás para frente vira 121-, com o sinal no fim. O 10 também não é, porque de trás para frente vira 01.

O valor de x fica entre -2³¹ e 2³¹ - 1, ou seja, entre -2.147.483.648 e 2.147.483.647. No fim do enunciado, o LeetCode propõe um desafio extra: resolver sem converter o número em texto.

Big O em poucas palavras

A notação Big O descreve como o custo de um algoritmo cresce quando a entrada cresce. Neste problema, a entrada é um número só. O que cresce é a quantidade de dígitos, chamada aqui de d. Um número com d dígitos fica entre 10ᵈ⁻¹ e 10ᵈ, por isso d cresce com o logaritmo de x na base 10. O(d) quer dizer que o trabalho cresce na mesma proporção da quantidade de dígitos. Também dá para escrever O(log x), que é a mesma coisa. Dentro do limite do problema, d vai no máximo até 10.

A complexidade de espaço segue a mesma ideia para a memória extra que o algoritmo usa. O(1) quer dizer que essa memória não muda com o tamanho do número.

Dois gráficos. À esquerda, a quantidade de dígitos sobe em degraus conforme o valor de x cresce em escala logarítmica, até 10 dígitos em 2³¹ - 1. À direita, as voltas do laço em palíndromos de 1 a 10 dígitos: a inversão do número inteiro faz d voltas, os dois ponteiros fazem d/2 comparações e a inversão da metade faz cerca de d/2 voltas

Figura 1. À esquerda, a quantidade de dígitos d cresce com log₁₀ x. À direita, as voltas do laço de cada solução em palíndromos de 1 a 10 dígitos, contadas executando os laços das soluções. Elaborado para este post.

Solução 1: comparar com o texto invertido

A ideia mais direta é transformar o número em texto com str e comparar com o mesmo texto de trás para frente. Em Python, o fatiamento texto[::-1] cria uma cópia invertida do texto.

def palindromo_string_invertida(x: int) -> bool:
    # Converte o número em texto e compara com o texto invertido
    # O fatiamento [::-1] cria uma cópia de trás para frente
    texto = str(x)
    return texto == texto[::-1]

O sinal de menos resolve sozinho o caso negativo. O texto de -121 é "-121", e o invertido é "121-". Os dois são diferentes, então a resposta é False. O 10 vira "10" e "01", que também são diferentes.

Três pares de linhas de caixas. Para 121, o texto e o texto invertido são iguais e aparecem em verde. Para -121 e 10, as posições diferentes aparecem em laranja e a comparação dá False

Figura 2. Comparação de cada texto com a sua cópia invertida para 121, -121 e 10. Em laranja, as posições em que os dois diferem. Elaborado para este post.

Complexidade de tempo: O(d). A conversão em texto, a cópia invertida e a comparação passam pelos d dígitos.

Complexidade de espaço: O(d). O código guarda dois textos de d caracteres, o original e a cópia invertida.

A cópia invertida é trabalho extra. Para saber se o texto é palíndromo, basta comparar cada caractere com o caractere da posição espelhada, sem montar o texto inteiro de novo.

Solução 2: dois ponteiros no texto

Esta versão também converte o número em texto, mas não cria a cópia invertida. Um ponteiro começa no primeiro caractere e outro no último. Se os dois caracteres são iguais, a esquerda avança e a direita recua. Se são diferentes, a resposta já é False. Quando os ponteiros se encontram no meio, todos os pares foram conferidos.

def palindromo_dois_ponteiros(x: int) -> bool:
    texto = str(x)
    esquerda, direita = 0, len(texto) - 1
    # Compara os caracteres das pontas e anda para o meio
    while esquerda < direita:
        if texto[esquerda] != texto[direita]:
            # Primeira diferença: já sabe que não é palíndromo
            return False
        esquerda += 1
        direita -= 1
    return True

Três passos dos ponteiros esquerda e direita no texto 12321. Nos passos 1 e 2, os caracteres das pontas são iguais. No passo 3, os ponteiros se encontram no 3 do meio e a função devolve True

Figura 3. Dois ponteiros no texto "12321". A cada passo, os caracteres das pontas são comparados e os ponteiros andam para o meio. Elaborado para este post.

Complexidade de tempo: O(d). No pior caso, o laço faz d/2 comparações, e a conversão em texto passa pelos d dígitos. Em um número que não é palíndromo, como 12345, o laço para na primeira diferença, que nesse caso é a primeira comparação.

Complexidade de espaço: O(d). Sai a cópia invertida, mas o texto com os d caracteres continua na memória.

As duas primeiras soluções dependem do texto, e o desafio extra do enunciado pede para resolver sem ele. A próxima versão trabalha só com contas.

Solução 3: inverter o número inteiro

Duas operações separam os dígitos de um número. O resto da divisão por 10 (x % 10) dá o último dígito. A divisão inteira por 10 (x // 10) tira esse dígito. Com 123, 123 % 10 dá 3 e 123 // 10 dá 12.

A função tira os dígitos de x um por um, do último para o primeiro, e monta outro número com eles. A cada volta, o número invertido é multiplicado por 10 e recebe o dígito novo no fim. No final, o número é palíndromo se for igual ao seu invertido. Os negativos ficam de fora logo no início, porque o sinal nunca aparece no fim.

def palindromo_inverte_numero(x: int) -> bool:
    # Número negativo nunca é palíndromo por causa do sinal
    if x < 0:
        return False
    original, invertido = x, 0
    while x > 0:
        # Tira o último dígito de x e coloca no fim de invertido
        invertido = invertido * 10 + x % 10
        x //= 10
    return original == invertido

Para 12321, o laço faz cinco voltas. O invertido passa por 1, 12, 123, 1232 e 12321. Como o resultado é igual ao original, a resposta é True. Para 10, o invertido termina como 1, que é diferente de 10.

Complexidade de tempo: O(d). O laço faz uma volta por dígito.

Complexidade de espaço: O(1). O código usa só três números, original, invertido e x, para qualquer quantidade de dígitos.

Esta versão tem um risco em linguagens como Java e C++, em que o int tem 32 bits. O invertido de um número válido pode passar do limite. O 2.147.483.647, por exemplo, invertido vira 7.463.847.412. Em Python os inteiros não têm esse limite, mas o problema continua: o laço inverte o número inteiro, quando metade bastaria.

Solução 4: inverter só a metade

Em um palíndromo, a metade da direita lida de trás para frente é igual à metade da esquerda. Por isso, basta inverter os dígitos até chegar ao meio. O laço tira dígitos de x e coloca em metade, como na solução 3. Ele para quando x fica menor ou igual a metade, porque nesse ponto os dígitos já passaram do meio.

def palindromo_metade(x: int) -> bool:
    # Negativos não são palíndromos
    # Terminado em 0 só é palíndromo se for o próprio 0
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    metade = 0
    # Inverte só os dígitos da direita até passar do meio
    while x > metade:
        metade = metade * 10 + x % 10
        x //= 10
    # Quantidade par de dígitos: as duas metades são iguais
    # Quantidade ímpar: o dígito do meio fica no fim de metade e é descartado
    return x == metade or x == metade // 10

A comparação final tem dois casos. Com quantidade par de dígitos, como em 1221, o laço para com x = 12 e metade = 12, e os dois são iguais. Com quantidade ímpar, como em 12321, o laço para com x = 12 e metade = 123. O dígito do meio, o 3, não precisa ser comparado com nada, então metade // 10 o descarta e sobra 12, igual a x.

Dois quadros lado a lado com os valores de x e metade a cada volta do laço. Para 1221, após duas voltas, x e metade valem 12. Para 12321, após três voltas, x vale 12 e metade vale 123, e metade dividido por 10 dá 12

Figura 4. Inversão da metade para 1221 e 12321. O laço para quando x fica menor ou igual a metade. Elaborado para este post.

A primeira linha da função trata um caso que o laço erraria. Um número terminado em 0, como 10 ou 1210, só seria palíndromo se começasse com 0, e nenhum número começa com 0. A única exceção é o próprio 0. Sem essa linha, o 10 passaria no teste. A primeira volta tira o 0 e deixa x = 1 e metade = 0. A segunda deixa x = 0 e metade = 1. Aí metade // 10 dá 0, igual a x, e a função devolveria True.

Complexidade de tempo: O(d). O laço faz cerca de d/2 voltas, e na notação Big O a constante 1/2 é descartada.

Complexidade de espaço: O(1). O código usa só x e metade.

Na notação Big O, as soluções 3 e 4 empatam. A solução 4 ganha na constante, com metade das voltas, e o número que ela monta não passa do limite de 32 bits, porque tem só cerca de metade dos dígitos de x.

Testes

O código das quatro funções deste post é o mesmo do script de testes, executado em Python 3.13.5. O script roda 16 casos fixos em cada solução: os 3 exemplos do enunciado e 13 casos extras, com zero, um dígito, quantidade par e ímpar de dígitos, número terminado em zero, zero no meio, números que diferem só no meio e os dois limites do intervalo. Depois, roda 12.000 números aleatórios: 10.000 sorteados em todo o intervalo e 1.000 palíndromos de 1 a 10 dígitos, cada um também com 1 somado. A resposta de cada solução é conferida com a definição de palíndromo. Ao todo, foram 48.064 verificações (16 × 4 + 12.000 × 4), todas corretas.

Comparação

A Figura 5 mostra o tempo de cada solução no pior caso, que é quando o número é palíndromo e todos os dígitos precisam ser conferidos. Para cada quantidade de dígitos, de 1 a 10, foram usados 200 palíndromos aleatórios. Cada medida chama a função 40.000 vezes, e cada ponto é o menor tempo de 7 medidas, dividido pelo número de chamadas.

Gráfico com o tempo por chamada, em nanossegundos, das quatro soluções do Palindrome Number para palíndromos de 1 a 10 dígitos. O texto invertido fica quase reto, perto de 70 ns, e a inversão do número inteiro sobe até cerca de 540 ns

Figura 5. Tempo por chamada de cada solução do Palindrome Number no pior caso, em nanossegundos, para palíndromos de 1 a 10 dígitos. Gráfico elaborado para este post com o script de testes, em Python 3.13.5.

O resultado contraria a ordem do post. Com 10 dígitos, o texto invertido levou 80 ns por chamada, os dois ponteiros levaram 242 ns, a inversão do número inteiro levou 537 ns e a inversão da metade levou 324 ns. Entre as duas soluções sem texto, a da metade foi cerca de 40% mais rápida, como prevê a metade das voltas. Mesmo assim, a solução 1 foi a mais rápida de todas, cerca de quatro vezes mais rápida que a solução 4.

O motivo está em quem faz o trabalho. Na solução 1, a conversão, a inversão e a comparação são funções internas do Python, escritas em C, e cada uma roda em uma única chamada. Nas soluções 2, 3 e 4, cada volta do laço roda como código Python, e cada volta custa dezenas de nanossegundos. Por isso o tempo da solução 1 quase não muda entre 1 e 10 dígitos (de 63 ns para 80 ns), enquanto o da solução 3 sobe de 82 ns para 537 ns. A curva da solução 4 sobe em zigue-zague porque, com quantidade ímpar de dígitos, ela faz uma volta a mais e precisa da segunda comparação do return.

Abordagem	Tempo	Espaço	Observação
Texto invertido	O(d)	O(d)	Mais simples. Em Python, foi a mais rápida, com 80 ns para 10 dígitos
Dois ponteiros no texto	O(d)	O(d)	Não cria a cópia invertida e para na primeira diferença
Inverte o número inteiro	O(d)	O(1)	Não usa texto, mas pode passar do limite de 32 bits em outras linguagens
Inverte só a metade	O(d)	O(1)	Metade das voltas e sem risco de passar do limite. Atende ao desafio extra

A solução 4 é a resposta ao desafio extra do enunciado e a que menos usa memória. Em Python, a solução 1 é mais curta e mais rápida. Em outra linguagem, a ordem dos tempos pode mudar, e só uma medição na própria linguagem confirma.

Próximo post da série

O próximo post da série LeetCode Easy, na sexta, 30/10, trata do problema 13, Roman to Integer. Ele pede para converter um número romano, como XIV, em um número inteiro. Os problemas 10 a 12 são de nível Medium ou Hard e ficam fora da série.

Os links da Amazon neste post são de afiliado: se você comprar por eles, recebo uma comissão, sem custo extra para você.

Para saber mais

Problema: 9. Palindrome Number, LeetCode.
Post anterior da série: LeetCode Easy 1: Two Sum em Python, de O(n²) a O(n).
Documentação: "Texto", seção 3.1.2 do tutorial oficial do Python, com índices e fatiamento de strings.
Documentação: "Operações binárias aritméticas", seção 6.7 da referência da linguagem Python, com os operadores // e %.
Documentação: módulo timeit, documentação oficial do Python. É o módulo usado para medir os tempos deste post.
Livro: Entendendo Algoritmos: um guia ilustrado para programadores e outros curiosos, de Aditya Y. Bhargava. 2ª edição, Novatec, 2026. ISBN 978-8575229293. Explica a notação Big O com ilustrações e exemplos em Python 3.
Livro: Cracking the Coding Interview: 189 Programming Questions and Solutions, de Gayle Laakmann McDowell. 6ª edição, CareerCup, 2015. ISBN 978-0984782857. Em inglês, com 189 questões de entrevista resolvidas e uma seção sobre notação Big O.