Check if a number is Palindrome or not

Home

Community

Blog Posts

Programming

Tech Topics

Explore

Find Jobs

Check if a number is Palindrome or not

Asked 1 year ago

0Comments

2 Views

Approch 1

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        // Numbers ending in 0 that are not 0 are not palindromes
        if (x != 0 && x % 10 == 0) {
            return false;
        }
        
        int result = 0;
        int temp = x;
        
        while(temp > 0) {
            int digit = temp % 10;
            result = result * 10 + digit;
            temp = temp / 10;
        }
        
        return result == x;
    }
};

Explanation:

Check if x is negative, return false immediately.
Check if x ends with 0 (and is not 0 itself), return false immediately.
Initialize result to 0 and temp to x.
Reverse x by extracting digits from temp and appending to result.
Compare reversed result with original x, return true if equal.

Test Case:

Input: x = 121

Dry Run:

x = 121, temp = 121, result = 0
digit = 121 % 10 = 1, result = 0 * 10 + 1 = 1, temp = 121 / 10 = 12
digit = 12 % 10 = 2, result = 1 * 10 + 2 = 12, temp = 12 / 10 = 1
digit = 1 % 10 = 1, result = 12 * 10 + 1 = 121, temp = 1 / 10 = 0
result == x, return true

Approach 2: Converting to String

Now, let's look at the second approach:

Approach 2: Converting to string and using two pointers

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        
        string str = to_string(x);
        int start = 0;
        int end = str.size() - 1;
        
        while (start < end) {
            if (str[start] != str[end]) {
                return false;
            }
            start++;
            end--;
        }
        
        return true;
    }
};

Let's dry run this with x = 12321:

Initial check: x is positive, so we proceed.
Convert to string: str = "12321"
Initialize: start = 0, end = 4
Loop iterations:
- Iteration 1: str[0] == str[4], start = 1, end = 3
- Iteration 2: str[1] == str[3], start = 2, end = 2
Loop ends (start is not < end)
Return true

This approach works by converting the number to a string and checking if it reads the same from both ends. It's more intuitive but involves string conversion.

Comparison:

Time Complexity: Both are O(log x) or O(n) where n is the number of digits.
Space Complexity:
- Approach 1: O(1), uses constant extra space.
- Approach 2: O(log x) for string conversion.
Readability: Approach 2 is generally more intuitive and easier to understand.
Performance: Approach 1 might be slightly faster for very large numbers as it avoids string conversion.

Both approaches are valid and have their merits. Approach 1 is more efficient in terms of space and potentially time for very large numbers, while Approach 2 is more straightforward and easier to understand at a glance. The choice between them might depend on specific requirements or preferences in a given situation.

Two Pointer

Basic

easy

Check if a number is Palindrome or not

Approch 1

Write your comment here !

0 Responses