NUHMAN.com

Introduction

The Palindrome Number problem on LeetCode is a straightforward yet interesting challenge that tests your understanding of number manipulation without relying on string conversions. In this article, we’ll solve LeetCode 9 in Go (Golang) using a clean and optimized approach that avoids converting the integer to a string.

Problem Statement

Given an integer x, return true if x is a palindrome, and false otherwise.

An integer is a palindrome when it reads the same backward as forward.

Example

go

Input: x = 121
Output: true
go

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-.
go

Input: x = 10
Output: false

Naive Approach: Convert to String

A simple way is to convert the integer to a string and check if the string is equal to its reverse. However, this isn't ideal for interview settings where you're often asked to solve it without string conversion.

Optimized Approach: Reverse Half the Number

Instead of reversing the whole number (which could cause overflow), reverse only half of the digits and compare with the remaining half.

Algorithm Steps:

1. Handle edge cases:

• Negative numbers are not palindromes.
• Numbers ending in 0 can't be palindromes (unless the number is 0).

1. Repeatedly take the last digit of x and build the reverse of half the number.
2. Stop when the reversed half is greater than or equal to the remaining half.
3. Compare the reversed half and the original half (or adjusted half for odd digits).

Go Implementation

go

package main

import (
    "fmt"
)

func isPalindrome(x int) bool {
    // Edge cases
    if x < 0 || (x%10 == 0 && x != 0) {
        return false
    }

    reversed := 0
    for x > reversed {
        lastDigit := x % 10
        reversed = reversed*10 + lastDigit
        x /= 10
    }

    // Even digits: x == reversed
    // Odd digits: x == reversed / 10 (middle digit doesn't matter)
    return x == reversed || x == reversed/10
}

func main() {
    inputs := []int{121, -121, 10, 12321, 0}

    for _, x := range inputs {
        fmt.Printf("Is %d a palindrome? %v\n", x, isPalindrome(x))
    }
}

How It Works

For x = 1221:

• Step 1: reversed = 1, x = 122
• Step 2: reversed = 12, x = 12
• Stop since x <= reversed
• Check x == reversed → true

For x = 12321:

• reversed = 1, x = 1232
• reversed = 12, x = 123
• reversed = 123, x = 12
• Now, x == reversed/10 → true

Time and Space Complexity

• Time Complexity: O(log₁₀(n)) — we're dividing the number by 10 in each iteration.
• Space Complexity: O(1) — no extra space used beyond variables.

Key Takeaways

• Avoid string conversion when asked — reverse digits using math.
• Check only half of the number to reduce complexity and avoid overflows.
• Be mindful of edge cases (negatives and trailing zeroes).