The O(n) Club: Palindrome Number—Mirror, Mirror on My Integer (No Strings, No Magic)

The O(n) Club: Palindrome Number—Mirror, Mirror on My Integer (No Strings, No Magic)

⚡ TL;DR

You want to check if a number looks the same backward and forward (like a digital taco-cat, but with actual tacos). Brute force is easy: make it a string, reverse, compare—but that won’t get you hired. Here’s how lazy devs do it:

// Don't show this to your interviewer
default:
public boolean isPalindrome(int x) {
    String s = Integer.toString(x);
    return s.equals(new StringBuilder(s).reverse().toString());
}

The grown-up version: reverse half the digits (math, not magic), compare, and boom! O(1) space, O(log x) time:

// Java: Reverse half the digits only
public boolean isPalindrome(int x) {
    if (x < 0 || (x != 0 && x % 10 == 0)) return false;
    int rev = 0;
    while (x > rev) {
        rev = rev * 10 + x % 10;
        x /= 10;
    }
    return (x == rev) || (x == rev / 10);
}

🧠 How Devs Usually Mess This Up

Classic rookie traps:

• String Transformation: Convert to string, reverse string, compare. It works, but at what cost (memory… respect…)?
• Negligent Negatives: Totally forgetting -121 isn’t a palindrome—unless you like imaginary number lines.
• The Zero-Finalist: Numbers ending in zero (e.g. 10) are not palindromes (unless they’re zero itself). If you think otherwise, let’s grab a coffee and discuss “01”.
• Full Integer Reversal Overflow: Hope you brought a helmet: giant numbers reversed fully crash and burn in Java.

🔍 What’s Actually Going On

Think of the number as a code reviewer with serious trust issues—they only care if the digits on the edges match up all the way to the middle, not what’s in-between. Reversing all digits is wasteful and dangerous; just reverse half.

It’s a two-runner relay: one starts at the left, one at the right, they sprint toward the middle. When they meet or pass, you check if the numbers they built are the same (or almost same, if there’s a solo digit in the middle). If yes, palindromic glory. If not, return the internet’s most polite “nope.” All in O(log x) time, O(1) space, so your CPU stays chill.

🛠️ PseudoCode

• Step 1: If x is negative or (ends with 0 but isn’t zero), return false.
  if (x < 0 || (x != 0 && x % 10 == 0)) return false;
• Step 2: Build rev = 0 to catch backward digits.
• Step 3: While x > rev:
  • Add last digit of x to rev: rev = rev * 10 + x % 10
  • Strip last digit from x: x /= 10
• Step 4: If x == rev (even digits) or x == rev / 10 (odd digits), it’s a palindrome. Job’s done.

💻 The Code

public class PalindromeChecker {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) return false;
        int reversedHalf = 0;
        while (x > reversedHalf) {
            reversedHalf = reversedHalf * 10 + x % 10;
            x /= 10;
        }
        // Works for both even and odd digit counts
        return x == reversedHalf || x == reversedHalf / 10;
    }
    public static void main(String[] args) {
        PalindromeChecker pc = new PalindromeChecker();
        System.out.println(pc.isPalindrome(121));    // true
        System.out.println(pc.isPalindrome(-121));   // false
        System.out.println(pc.isPalindrome(10));     // false
        System.out.println(pc.isPalindrome(0));      // true
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Negative Numbers: Palindromes are for the living (in math terms, positive numbers only).
• Trailing Zeroes: 10, 100, etc. are out—unless you enjoy wild interpretations of digit symmetry.
• Overflow Aversion: This approach never tries to hold the whole thing reversed—so even 2147483647 gets a fair shot.
• Time: O(log x) — barely enough for your caffeine crash to start.
• Memory: O(1). Unless you’re counting the emotional baggage of too many failed interviews.

🧠 Interviewer Brain-Tattoo

“If you’re about to call ‘toString’, just think how much your interviewer believes in you—and then don’t do it.”