Skip to main content

Leetcode 9: Palindrome Number


1. Problem Statement (Simple Explanation):


You are given an integer x.

Return:

  • true if x is a palindrome.

  • false otherwise.

A palindrome reads the same forward and backward.


2. Examples:


Example 1:

Input: x = 121

Output: true

Explanation:
 121 reads the same from left to right and right to left.


Example 2:

Input: x = -121

Output: false

Explanation:
 Left to right: -121
 Right to left: 121-
 Not the same → not a palindrome.


Example 3:

Input: x = 10

Output: false

Explanation:
 Reversed digits → 01, which is 1, not equal to 10.


Constraints:

-231 ≤ x ≤ 231-1


Follow-up: Solve without converting the integer to a string.


3. Approach 1 – String Conversion (Straightforward, But Not Follow-up):


Intuition:


  • Convert the integer to a string.

  • Check if the string is equal to its reverse.

Edge cases:

  • Negative numbers automatically not palindromes (because of '-' sign).


Algorithm (String-based):


  1. If x < 0, return false.

  2. Convert x to string s.

  3. Check if s == reverse(s).

  4. Return that boolean.


Pseudo-code (String Approach):



Complexity:


Let k be number of digits:

  • Time: O(k)

  • Space: O(k) for string.

Simple, but doesn’t meet the follow-up requirement.


4. Approach 2 – Reverse the Whole Number (No String, But Risky for Overflow):


We can reuse logic similar to “Reverse Integer”:

  • Reverse the entire integer.

  • Compare reversed value with original.

But reversing the full integer can overflow a 32-bit integer, and you’d need to handle that carefully.

There is a better integer-only method that avoids overflow and extra work: reverse half the number.


5. Approach 3 – Reverse Half the Digits (Optimal, Integer-only):


This is the standard follow-up solution.


Key Ideas:


  1. Negative numbers are not palindromes (due to '-').

  2. Any positive number ending with 0 (and not equal to 0 itself) cannot be a palindrome:

    • Example: 10, 100, 120 etc.

  3. Instead of reversing the entire number, we reverse only the last half of the digits and compare with the first half.


How Half-Reversal Works:


Let x be non-negative and not ending with zero (unless it is zero):

We maintain reversedHalf:

  • Repeatedly:

    • Take last digit of x (via % 10) and add it to reversedHalf.

    • Remove last digit from x (via / 10).

  • We stop when reversedHalf >= x.

At that point:

  • For even number of digits:

    • x == reversedHalf if palindrome.

  • For odd number of digits:

    • Middle digit is in reversedHalf (e.g., 12321 → eventually x = 12, reversedHalf = 123).

    • We can remove the middle digit from reversedHalf by integer division by 10.

    • Then check x == reversedHalf / 10.


Algorithm (Step-by-Step):


  1. If x < 0: return false.

  2. If x != 0 and x % 10 == 0: return false.

    • Numbers like 10, 100, 120 cannot be palindromes.

  3. Initialize reversedHalf = 0.

  4. While x > reversedHalf:

    • digit = x % 10

    • reversedHalf = reversedHalf * 10 + digit

    • x = x / 10 (integer division)

  5. After loop:

    • If x == reversedHalf → even number of digits → palindrome.

    • Else if x == reversedHalf / 10 → odd number of digits → palindrome.

    • Else → not a palindrome.


Pseudo-code (Half Reversal, Recommended):



Complexity:


Let k be number of digits:

  • Time: O(k)

  • Space: O(1)

We reverse only half the digits, so it’s safe from overflow and efficient.


6. Java code:



7. C code:



8. C++ code:



9. Python code:



10. JavaScript code:





<<<PREV
NEXT>>>

Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more