Ebenezer

Posted on Jun 7

Palindrome Number — My Beginner Thinking Process, Pseudocode & Optimal Solution

#probelemsolving #beginners #programming

Hey Folks! 👋

Good Day...

As I shared in my previous blog, I have started a new problem-solving practice routine. From today onwards, I'll be working on some of the most commonly asked interview questions that developers often encounter during coding interviews. These problems are also popular on LeetCode, making them a great way to strengthen both problem-solving skills and coding fundamentals.
Today I solved one of the most famous beginner-friendly LeetCode problems: Palindrome Number.

At first, I wasn't thinking about code. I was thinking about the pattern.

Problem Statement

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

Example

121  -> true

-121 -> false

10   -> false

A palindrome reads the same from left to right and right to left.

My Initial Thinking (Two Pointer Approach)

Before writing any code, I drew the number on paper.

For example:

1 2 1 2 1
↑       ↑
L       R

I started comparing the first and last digits.

1 == 1 

2 == 2

Eventually both pointers meet in the middle.

Since every comparison matched, the number is a palindrome.

My thought process was:

Compare left digit with right digit.

If both are same:
    Move inward.

If different:
    Not a palindrome.

This is exactly how humans check a palindrome.

Rule #1: Negative Numbers Are Never Palindromes

Example:

-121

Read from left to right:

-121

Read from right to left:

121-

Both are different.

Therefore:

Any negative number is NOT a palindrome.

Rule #2: Numbers Ending With 0 Are Not Palindromes

Example:

Reverse:

Which becomes:

Not the same.

Therefore:

If a number ends with 0 and is not 0 itself,
it cannot be a palindrome.

Examples:

10   
100  
120

But:

is a palindrome.

Moving From Pointer Thinking to Math Thinking

My initial idea was based on pointers.

However, LeetCode asks:

Can you solve it without converting the integer into a string?

That means we cannot use:

String.valueOf(x)

Instead, we need to work directly with digits.

We can extract digits using:

x % 10

and remove digits using:

x / 10

Beginner-Friendly Pseudocode

This is the pseudocode I understood before writing Java.

If number is negative
    Return false

If number ends with 0 and is not 0
    Return false

Create reversedHalf = 0

While original number is greater than reversedHalf

    Take the last digit

    Add that digit into reversedHalf

    Remove last digit from original number

For even length numbers:
    Compare original number and reversedHalf

For odd length numbers:
    Compare original number and reversedHalf/10

Return result

Understanding rev / 10

This confused me initially.

Let's take:

After processing:

x   = 1
rev = 12

Notice that:

rev
↓
1 2

The middle digit got included.

The middle digit doesn't need comparison because it has no pair.

So we remove it:

rev / 10

12 / 10 = 1

Now:

x = 1
rev/10 = 1

Match found

That's why the final condition is:

x == rev || x == rev / 10

Optimal Java Solution

class Solution {
    public boolean isPalindrome(int x) {

        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int rev = 0;

        while (x > rev) {
            int digit = x % 10;
            rev = rev * 10 + digit;
            x = x / 10;
        }

        return x == rev || x == rev / 10;
    }
}

Output

For input:

Output:

true

I verified the solution on LeetCode and it was accepted successfully.

Time Complexity

O(log₁₀ n)

We process only half of the digits.

Space Complexity

O(1)

No extra array, string, or collection is used.

Thanks for reading!

If you're also learning Data Structures & Algorithms as a beginner, feel free to share how you initially thought about this problem. Sometimes your thinking teaches more than an advanced solution.

DEV Community