Palindrome Number

🎯

Palindrome Number

easyMATHAmazonGoogleFacebook

Imagine you are building a system that validates user IDs which must read the same forwards and backwards to ensure symmetry and ease of recall.

💡 This problem tests understanding of number manipulation and symmetry. Beginners often struggle with reversing digits without converting to strings or handling negative numbers correctly.

📋

Problem Statement

Given an integer x, determine whether it is a palindrome. An integer is a palindrome when it reads the same backward as forward. Return true if x is a palindrome, and false otherwise.

-2^31 <= x <= 2^31 - 1

💡

Example

Input"121"

Outputtrue

Reading 121 from left to right and right to left is the same.

Input"-121"

Outputfalse

Negative numbers are not palindromes because of the '-' sign.

Input"10"

Outputfalse

Reading 10 backward is 01 which is not the same.

• 0 → true (single digit is always palindrome)
• -101 → false (negative number)
• 1001 → true (even length palindrome)
• 100 → false (trailing zeroes break palindrome)

⚠️

Common Mistakes

Not handling negative numbers

Returns true incorrectly for negative inputs

✅ Add explicit check for x < 0 and return false

Ignoring trailing zeros

Returns true for numbers like 10 which are not palindromes

✅ Check if number ends with zero but is not zero itself and return false

Reversing entire number causing overflow

Runtime error or incorrect result for large inputs

✅ Use half reversal approach to avoid overflow

Comparing reversed number with modified original incorrectly

False negatives for odd length palindromes

✅ Compare original with reversed half or reversed half divided by 10

Using string conversion in performance-critical contexts

Slower performance and higher memory usage

✅ Use numeric reversal approaches for optimal performance

🧠

Brute Force (String Conversion)

💡 This approach is straightforward and helps beginners understand the palindrome concept by converting the number to a string and checking symmetry.

Intuition

Convert the integer to a string and check if the string reads the same forwards and backwards.

Algorithm

1. Convert the integer to a string.
2. Use two pointers: one at the start and one at the end of the string.
3. Compare characters at both pointers.
4. If all pairs match, return true; otherwise, return false.

💡 Using two pointers is a common pattern to check symmetry, but converting to string is not always optimal.

</>

Code

def is_palindrome(x: int) -> bool:
    s = str(x)
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

# Driver code
if __name__ == '__main__':
    test_cases = [121, -121, 10, 0]
    for num in test_cases:
        print(f'is_palindrome({num}) = {is_palindrome(num)}')

Line Notes

s = str(x)Convert integer to string to enable character-wise comparison.

left, right = 0, len(s) - 1Initialize two pointers at the start and end of the string.

while left < right:Loop until pointers meet or cross, checking pairs.

if s[left] != s[right]:If mismatch found, number is not palindrome.

return TrueIf loop completes without mismatch, number is palindrome.

public class PalindromeNumber {
    public static boolean isPalindrome(int x) {
        String s = Integer.toString(x);
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] testCases = {121, -121, 10, 0};
        for (int num : testCases) {
            System.out.println("isPalindrome(" + num + ") = " + isPalindrome(num));
        }
    }
}

Line Notes

String s = Integer.toString(x);Convert integer to string for easy character access.

int left = 0, right = s.length() - 1;Set pointers at string boundaries.

while (left < right)Loop to compare characters from both ends.

if (s.charAt(left) != s.charAt(right))Detect mismatch to return false early.

return true;Return true if all characters match.

#include <iostream>
#include <string>
using namespace std;

bool isPalindrome(int x) {
    string s = to_string(x);
    int left = 0, right = s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    int testCases[] = {121, -121, 10, 0};
    for (int num : testCases) {
        cout << "isPalindrome(" << num << ") = " << (isPalindrome(num) ? "true" : "false") << endl;
    }
    return 0;
}

Line Notes

string s = to_string(x);Convert integer to string for easy digit comparison.

int left = 0, right = s.size() - 1;Initialize two pointers at string ends.

while (left < right)Loop to check characters from both ends.

if (s[left] != s[right])Return false immediately if mismatch found.

return true;Return true if all pairs match.

function isPalindrome(x) {
    const s = x.toString();
    let left = 0, right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// Test cases
[121, -121, 10, 0].forEach(num => {
    console.log(`isPalindrome(${num}) = ${isPalindrome(num)}`);
});

Line Notes

const s = x.toString();Convert number to string for easy indexing.

let left = 0, right = s.length - 1;Set pointers at string boundaries.

while (left < right)Loop to compare characters from both ends.

if (s[left] !== s[right])Return false if characters differ.

return true;Return true if no mismatches found.

⏱

Complexity

TimeO(n)

SpaceO(n)

Converting to string takes O(n) time and space where n is number of digits; two-pointer check is O(n/2).

💡 For a 5-digit number, this means about 5 operations to convert and 2-3 comparisons.

Interview Verdict: Accepted

This approach is accepted but not optimal; good for initial understanding and quick implementation.

🧠

Better (Digit Reversal with Full Number)

💡 This approach avoids string conversion by reversing the entire number mathematically, reinforcing digit manipulation skills.

Intuition

Reverse the integer by extracting digits and reconstructing the reversed number, then compare with original.

Algorithm

1. If number is negative, return false immediately.
2. Initialize reversed number to 0.
3. Extract last digit of x and append to reversed number.
4. Remove last digit from x by integer division.
5. Repeat until x is 0.
6. Compare reversed number with original input.

💡 The challenge is to reverse digits without losing precision or causing overflow.

</>

Code

def is_palindrome(x: int) -> bool:
    if x < 0:
        return False
    original = x
    reversed_num = 0
    while x > 0:
        digit = x % 10
        reversed_num = reversed_num * 10 + digit
        x //= 10
    return original == reversed_num

# Driver code
if __name__ == '__main__':
    test_cases = [121, -121, 10, 0]
    for num in test_cases:
        print(f'is_palindrome({num}) = {is_palindrome(num)}')

Line Notes

if x < 0:Negative numbers cannot be palindromes due to the minus sign.

original = xStore original number for final comparison.

digit = x % 10Extract last digit of current number.

reversed_num = reversed_num * 10 + digitAppend extracted digit to reversed number.

x //= 10Remove last digit from number by integer division.

return original == reversed_numCheck if reversed number matches original.

public class PalindromeNumber {
    public static boolean isPalindrome(int x) {
        if (x < 0) return false;
        int original = x;
        int reversed = 0;
        while (x > 0) {
            int digit = x % 10;
            reversed = reversed * 10 + digit;
            x /= 10;
        }
        return original == reversed;
    }

    public static void main(String[] args) {
        int[] testCases = {121, -121, 10, 0};
        for (int num : testCases) {
            System.out.println("isPalindrome(" + num + ") = " + isPalindrome(num));
        }
    }
}

Line Notes

if (x < 0) return false;Immediately exclude negative numbers.

int original = x;Keep original number for comparison.

int digit = x % 10;Extract last digit of current number.

reversed = reversed * 10 + digit;Build reversed number digit by digit.

x /= 10;Remove last digit from number.

return original == reversed;Check palindrome condition.

#include <iostream>
using namespace std;

bool isPalindrome(int x) {
    if (x < 0) return false;
    int original = x;
    int reversed = 0;
    while (x > 0) {
        int digit = x % 10;
        reversed = reversed * 10 + digit;
        x /= 10;
    }
    return original == reversed;
}

int main() {
    int testCases[] = {121, -121, 10, 0};
    for (int num : testCases) {
        cout << "isPalindrome(" << num << ") = " << (isPalindrome(num) ? "true" : "false") << endl;
    }
    return 0;
}

Line Notes

if (x < 0) return false;Exclude negative numbers early.

int original = x;Store original number for final check.

int digit = x % 10;Extract last digit for reversal.

reversed = reversed * 10 + digit;Append digit to reversed number.

x /= 10;Remove last digit from number.

return original == reversed;Compare reversed with original.

function isPalindrome(x) {
    if (x < 0) return false;
    let original = x;
    let reversed = 0;
    while (x > 0) {
        let digit = x % 10;
        reversed = reversed * 10 + digit;
        x = Math.floor(x / 10);
    }
    return original === reversed;
}

// Test cases
[121, -121, 10, 0].forEach(num => {
    console.log(`isPalindrome(${num}) = ${isPalindrome(num)}`);
});

Line Notes

if (x < 0) return false;Negative numbers are not palindromes.

let original = x;Keep original number for comparison.

let digit = x % 10;Extract last digit for reversal.

reversed = reversed * 10 + digit;Build reversed number incrementally.

x = Math.floor(x / 10);Remove last digit by integer division.

return original === reversed;Check if reversed equals original.

⏱

Complexity

TimeO(n)

SpaceO(1)

Reversing digits takes O(n) time where n is number of digits; space is constant as no extra string is created.

💡 For a 5-digit number, about 5 iterations are needed, but no extra memory is used.

Interview Verdict: Accepted

This approach is more optimal than string conversion and preferred in interviews.

🧠

Optimal (Reverse Half the Number)

💡 This approach optimizes by reversing only half the digits, avoiding overflow and unnecessary computation.

Intuition

Reverse the last half of the digits and compare with the first half to determine palindrome status.

Algorithm

1. If number is negative or ends with zero (but not zero itself), return false.
2. Initialize reversed half to 0.
3. While original number is greater than reversed half, extract last digit and append to reversed half.
4. After loop, compare original number with reversed half or reversed half divided by 10 (for odd length).
5. Return true if equal, false otherwise.

💡 The key insight is that only half the digits need to be reversed to check palindrome.

</>

Code

def is_palindrome(x: int) -> bool:
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    reversed_half = 0
    while x > reversed_half:
        reversed_half = reversed_half * 10 + x % 10
        x //= 10
    return x == reversed_half or x == reversed_half // 10

# Driver code
if __name__ == '__main__':
    test_cases = [121, -121, 10, 0, 12321, 123321]
    for num in test_cases:
        print(f'is_palindrome({num}) = {is_palindrome(num)}')

Line Notes

if x < 0 or (x % 10 == 0 and x != 0):Exclude negative numbers and numbers ending with zero except zero itself.

reversed_half = 0Initialize reversed half number.

while x > reversed_half:Reverse digits until half or more is reversed.

reversed_half = reversed_half * 10 + x % 10Append last digit of x to reversed half.

x //= 10Remove last digit from x.

return x == reversed_half or x == reversed_half // 10Check palindrome for even and odd length numbers.

public class PalindromeNumber {
    public static boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int reversedHalf = 0;
        while (x > reversedHalf) {
            reversedHalf = reversedHalf * 10 + x % 10;
            x /= 10;
        }
        return x == reversedHalf || x == reversedHalf / 10;
    }

    public static void main(String[] args) {
        int[] testCases = {121, -121, 10, 0, 12321, 123321};
        for (int num : testCases) {
            System.out.println("isPalindrome(" + num + ") = " + isPalindrome(num));
        }
    }
}

Line Notes

if (x < 0 || (x % 10 == 0 && x != 0)) return false;Exclude invalid palindrome candidates early.

int reversedHalf = 0;Store reversed half of the number.

while (x > reversedHalf)Reverse digits until half is processed.

reversedHalf = reversedHalf * 10 + x % 10;Append last digit to reversed half.

x /= 10;Remove last digit from x.

return x == reversedHalf || x == reversedHalf / 10;Check palindrome for even and odd length.

#include <iostream>
using namespace std;

bool isPalindrome(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int reversedHalf = 0;
    while (x > reversedHalf) {
        reversedHalf = reversedHalf * 10 + x % 10;
        x /= 10;
    }
    return x == reversedHalf || x == reversedHalf / 10;
}

int main() {
    int testCases[] = {121, -121, 10, 0, 12321, 123321};
    for (int num : testCases) {
        cout << "isPalindrome(" << num << ") = " << (isPalindrome(num) ? "true" : "false") << endl;
    }
    return 0;
}

Line Notes

if (x < 0 || (x % 10 == 0 && x != 0)) return false;Exclude negative and trailing zero numbers early.

int reversedHalf = 0;Initialize reversed half number.

while (x > reversedHalf)Reverse digits until half is processed.

reversedHalf = reversedHalf * 10 + x % 10;Append last digit to reversed half.

x /= 10;Remove last digit from x.

return x == reversedHalf || x == reversedHalf / 10;Check palindrome for even and odd length numbers.

function isPalindrome(x) {
    if (x < 0 || (x % 10 === 0 && x !== 0)) return false;
    let reversedHalf = 0;
    while (x > reversedHalf) {
        reversedHalf = reversedHalf * 10 + x % 10;
        x = Math.floor(x / 10);
    }
    return x === reversedHalf || x === Math.floor(reversedHalf / 10);
}

// Test cases
[121, -121, 10, 0, 12321, 123321].forEach(num => {
    console.log(`isPalindrome(${num}) = ${isPalindrome(num)}`);
});

Line Notes

if (x < 0 || (x % 10 === 0 && x !== 0)) return false;Exclude negative and trailing zero numbers early.

let reversedHalf = 0;Initialize reversed half number.

while (x > reversedHalf)Reverse digits until half is processed.

reversedHalf = reversedHalf * 10 + x % 10;Append last digit to reversed half.

x = Math.floor(x / 10);Remove last digit from x.

return x === reversedHalf || x === Math.floor(reversedHalf / 10);Check palindrome for even and odd length numbers.

⏱

Complexity

TimeO(log10(n))

SpaceO(1)

Only half the digits are processed, so time complexity is proportional to half the number of digits.

💡 For a 6-digit number, only about 3 iterations are needed, making it very efficient.

Interview Verdict: Accepted

This is the most optimal and recommended approach in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal half-reversal approach is recommended for coding in interviews due to its efficiency and elegance.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (String Conversion)	O(n)	O(n)	No	N/A	Mention only - quick to implement but not optimal
2. Better (Full Number Reversal)	O(n)	O(1)	No	N/A	Good to code if string conversion is disallowed
3. Optimal (Half Number Reversal)	O(log10(n))	O(1)	No	N/A	Best approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and ask about negative numbers.Step 2: Present brute force string conversion approach to confirm understanding.Step 3: Discuss numeric reversal approach to avoid string overhead.Step 4: Present optimal half-reversal approach for best efficiency.Step 5: Code the optimal approach and test edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests understanding of digit manipulation, edge case handling, and ability to optimize from naive to efficient solutions.

Common Follow-ups

• How to handle overflow when reversing digits → Use half reversal to avoid overflow.
• Can this be done without converting to string → Yes, by numeric reversal approaches.

💡 These follow-ups test deeper understanding of numeric operations and edge cases.

🔍

Pattern Recognition

When to Use

1) Problem asks if a number reads the same forwards and backwards, 2) Input is an integer, 3) Constraints allow digit manipulation, 4) Negative numbers or trailing zeros are special cases.

Signature Phrases

reads the same backward as forwardinteger palindrome check

NOT This Pattern When

Problems involving substring palindromes or palindrome partitioning which require dynamic programming.

Similar Problems

Palindrome Linked List - similar symmetry check but on linked list nodesValid Palindrome - checks palindrome on strings with filtering

Practice

1. You are given a string representing a column title as it appears in an Excel sheet (e.g., "A", "AB", "ZY"). Which algorithmic approach guarantees an optimal and efficient conversion of this title to its corresponding column number?

easy

A. Greedy approach that picks the highest value letter first and sums values

B. Iterative conversion treating the string as a base-26 number and accumulating the result

C. Dynamic programming to store intermediate sums for all prefixes

D. Recursive backtracking to try all possible letter combinations

Solution

1. Step 1: Understand the problem as base-26 conversion

   The Excel column title can be viewed as a number in base 26, where 'A' = 1, 'B' = 2, ..., 'Z' = 26.

2. Step 2: Identify the approach that accumulates values iteratively

   The iterative approach multiplies the current result by 26 and adds the value of the current character, effectively converting base-26 to decimal.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Iterative base-26 conversion matches Excel column numbering [OK]

Hint: Treat the string as a base-26 number [OK]

Common Mistakes:

• Using greedy or DP unnecessarily
• Recursion causes overhead
• Misinterpreting letter values

2. Identify the bug in the following code snippet that calculates the angle between clock hands:

class ClockAngle:
    def __init__(self):
        self.precomputed = [[0]*60 for _ in range(12)]
        for h in range(12):
            for m in range(60):
                hour_angle = h * 30  # Bug here
                minute_angle = m * 6
                diff = abs(hour_angle - minute_angle)
                self.precomputed[h][m] = min(diff, 360 - diff)

    def angleClock(self, hour: int, minutes: int) -> float:
        return self.precomputed[hour % 12][minutes]

medium

A. Line calculating hour_angle ignores minute progress, should be h * 30 + m * 0.5

B. Line calculating minute_angle should use (m % 60) * 6 to handle invalid minutes

C. Line computing diff should use (hour_angle + minute_angle) instead of abs difference

D. Line returning precomputed angle should use hour instead of hour % 12

Solution

1. Step 1: Analyze hour_angle calculation

   Hour hand moves 30 degrees per hour plus 0.5 degrees per minute. Ignoring minutes causes incorrect angles at times like 3:30.

2. Step 2: Verify other lines

   Minute angle calculation is correct, diff uses absolute difference properly, and hour modulo 12 is correct for indexing.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing minute contribution in hour_angle -> wrong angle [OK]

Hint: Hour hand moves continuously with minutes, not just discrete hours [OK]

Common Mistakes:

• Ignoring minute progress in hour hand angle
• Not normalizing hour to 12-hour format

3. What is the time complexity of the optimal approach that uses a hash set and checks pairs of points as diagonals to find the minimum area rectangle, given n points?

medium

A. O(n^4) because all quadruples of points are checked

B. O(n^2) because all pairs of points are checked and hash set lookups are O(1)

C. O(n^3) because for each pair, a linear search is done for complementary points

D. O(n log n) because points are sorted and then pairs are checked

Solution

1. Step 1: Identify loops in the optimal approach

   The code iterates over all pairs of points (i,j), which is O(n^2).

2. Step 2: Analyze point existence checks

   Checking if complementary points exist uses a hash set with O(1) average lookup, so no extra multiplicative factor.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Double loop + O(1) lookup -> O(n^2) time [OK]

Hint: Pairs checked, hash lookups O(1) -> O(n^2) [OK]

Common Mistakes:

• Confusing with brute force O(n^4)
• Assuming linear search inside pairs causes O(n^3)

4. The following code attempts to check if two rectangles overlap. Which line contains a subtle bug that causes incorrect results when rectangles only touch at edges or corners?

medium

A. Line 4: Return condition using '>=' instead of '>'

B. Line 2: Calculation of x_overlap

C. Line 1: Function definition

D. Line 3: Calculation of y_overlap

Solution

1. Step 1: Understand overlap condition

   Rectangles overlap only if overlap length on both axes is strictly greater than zero.

2. Step 2: Identify the bug in return condition

   Using '>=' returns true even when rectangles just touch edges (overlap = 0), which is incorrect.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Change '>=' to '>' fixes false positives on touching edges [OK]

Hint: Overlap must be strictly positive, not zero [OK]

Common Mistakes:

• Using '>=' instead of '>' in overlap check
• Mixing up min and max in coordinate calculations
• Ignoring one axis overlap

5. Suppose you want to find the nth ugly number but now the problem allows reusing the same ugly number multiple times in the heap without tracking duplicates. Which modification to the algorithm is necessary to maintain correctness and efficiency?

hard

A. Use three pointers to generate multiples in sorted order instead of a heap to avoid duplicates without tracking.

B. Remove the seen set and rely on the heap to naturally order numbers, accepting duplicates.

C. Keep the seen set but reset it periodically to allow reuse of numbers after some iterations.

D. Use a hash map to count occurrences of each ugly number and only push when count is below a threshold.

Solution

1. Step 1: Understand the impact of removing duplicate tracking

   Without a seen set, duplicates flood the heap, causing inefficiency and incorrect nth number.

2. Step 2: Identify alternative approach to avoid duplicates

   The three-pointer method generates ugly numbers in sorted order without duplicates by merging multiples of 2, 3, and 5.

3. Step 3: Conclude the necessary modification

   Switching to the three-pointer approach avoids duplicates inherently, maintaining correctness and efficiency.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Three-pointer approach is standard for duplicate-free generation without extra sets [OK]

Hint: Three-pointer method avoids duplicates without extra memory [OK]

Common Mistakes:

• Assuming heap alone can handle duplicates efficiently
• Trying to reset or partially track duplicates incorrectly
• Using counters without clear threshold logic