algoadvance

Leetcode 9. Palindrome Number

Problem Statement

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow-up: Could you solve it without converting the integer to a string?

Clarifying Questions

  1. Q: Should the solution handle negative numbers? A: No, negative numbers are not considered palindromes since they include a negative sign.

  2. Q: What about single-digit numbers? A: Single-digit numbers are always palindromes.

Strategy

  1. Check if the input number is negative. If it is, return false immediately.
  2. Reverse the second half of the number and compare it to the first half to determine if the number is a palindrome:
    • Initialize reversedNumber to 0.
    • Continue to extract digits from the end of the number and append to reversedNumber until originalNumber is less than or equal to reversedNumber.
  3. Finally, compare the partially reversed number with the remaining number.

Code

#include <iostream>

bool isPalindrome(int x) {
    // Early exit for negative numbers and multiples of 10 (except zero)
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    
    int reversedNumber = 0;
    while (x > reversedNumber) {
        reversedNumber = reversedNumber * 10 + x % 10;
        x /= 10;
    }
    
    // Handles both even and odd length numbers
    return x == reversedNumber || x == reversedNumber / 10;
}

int main() {
    // Test cases
    std::cout << std::boolalpha;
    std::cout << "121 is palindrome: " << isPalindrome(121) << std::endl;
    std::cout << "-121 is palindrome: " << isPalindrome(-121) << std::endl;
    std::cout << "10 is palindrome: " << isPalindrome(10) << std::endl;
    std::cout << "123321 is palindrome: " << isPalindrome(123321) << std::endl;

    return 0;
}

Time Complexity

This approach ensures that we solve the problem without converting the integer to a string and is efficient in terms of both time and space complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI