LeetCode 9 Solution - Palindrome Number

 

Problem Statement (LeetCode 9)

Given an integer x, return true if x is a palindrome integer.
An integer is a palindrome when it reads the same forward and backward.

Examples

Example 1

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and right to left.

Example 2

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-, which is not the same.

Example 3

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Not a palindrome.

Constraints

• -2³¹ <= x <= 2³¹ - 1

Edge Cases to Consider

✅ Negative numbers are never palindromes (e.g., -121).
✅ Single-digit numbers are always palindromes (e.g., 7).
✅ Numbers ending with 0 (except 0 itself) can never be palindromes (e.g., 10).

---

Optimal Approach: Reverse Half of the Number (O(log n) Time)

Intuition

• Instead of reversing the full number (which can cause overflow), we reverse only half.
• Compare the first half with the reversed second half.
• If they match, the number is a palindrome.

Key Observations

1. Negative numbers are never palindromes → Return false.
2. Last digit 0 means it cannot be a palindrome (unless it's 0).
3. Only reverse half of the digits instead of the full number.

---

LeetCode-Compatible C++ Code

class Solution {
public:
    bool isPalindrome(int x) {
        // Edge cases: Negative numbers or multiples of 10 (except 0) are not palindromes
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;

        int reversedHalf = 0;
        while (x > reversedHalf) {
            reversedHalf = reversedHalf * 10 + x % 10;
            x /= 10;
        }

        // The number is a palindrome if the first half equals the reversed second half
        return (x == reversedHalf || x == reversedHalf / 10);
    }
};

---

Step-by-Step Explanation

Example 1: x = 1221

Initial: x = 1221, reversedHalf = 0

Step 1: Extract last digit
    reversedHalf = 0 * 10 + 1221 % 10 = 1
    x = 1221 / 10 = 122

Step 2: Extract last digit
    reversedHalf = 1 * 10 + 122 % 10 = 12
    x = 122 / 10 = 12

Now, x (12) == reversedHalf (12) → Return true.

✅ Palindrome!

---

Example 2: x = 12345

Initial: x = 12345, reversedHalf = 0

Step 1: reversedHalf = 5, x = 1234
Step 2: reversedHalf = 54, x = 123
Step 3: reversedHalf = 543, x = 12

Now, x (12) != reversedHalf (543) → Return false.

❌ Not a palindrome!

---

Why This Approach is Best

Approach	Time Complexity	Space Complexity	Why?
Reverse Half (Best)	O(log n)	O(1)	Efficient, avoids overflow.
Full Reverse & Compare	O(log n)	O(1)	Can cause integer overflow.
Convert to String & Compare	O(n)	O(n)	Uses extra memory.

---

Alternative Approaches & Why Not?

1️⃣ Full Reverse and Compare

• Reverse the entire number and compare with the original.
• Problem: May cause integer overflow when reversing large numbers.
• Time Complexity: O(log n) (same as optimal).
• Space Complexity: O(1).

Code

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;

        long reversedNum = 0, original = x;
        while (x > 0) {
            reversedNum = reversedNum * 10 + x % 10;
            x /= 10;
        }

        return reversedNum == original;
    }
};

❌ Not preferred due to possible integer overflow.

---

2️⃣ Convert to String & Reverse

• Convert x to a string, reverse it, and compare.
• Problem: Uses extra memory (O(n)).
• Time Complexity: O(n) (string manipulation).

Code

class Solution {
public:
    bool isPalindrome(int x) {
        string s = to_string(x);
        string rev = s;
        reverse(rev.begin(), rev.end());
        return s == rev;
    }
};

❌ Not optimal due to extra space usage.

---

Conclusion

✅ Best approach: Reverse half of the number and compare.
✅ Avoids integer overflow while maintaining O(log n) time complexity.
✅ Uses only O(1) extra space.

Recommended Problems for Practice

1. Reverse Integer 🔄
2. Valid Palindrome 🔢
3. Palindrome Linked List 🧩

🚀 Master Palindrome Techniques with Efficient Solutions!