No result illustrationNo result illustration

DevLoom

search

Lets Connect

chevron right
Menu
Home

Home

Community

Community

Blog Posts

Blog Posts

Programming

Programming

Tech Topics

Tech Topics

Explore

Explore

Find Jobs

Find Jobs

Tags

Tags

DevLoomPerfect Place for devs
    profile

    Jubair

    upvoteupvote

    1

    downvote

    0

    star

    Check if a number is Palindrome or not

    clock icon

    Asked 11 months ago

    message

    0Comments

    eye

    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:
    1. Check if x is negative, return false immediately.
    2. Check if x ends with 0 (and is not 0 itself), return false immediately.
    3. Initialize result to 0 and temp to x.
    4. Reverse x by extracting digits from temp and appending to result.
    5. Compare reversed result with original x, return true if equal.
    Test Case:
    Input: x = 121
    Dry Run:
    1. x = 121, temp = 121, result = 0
    2. digit = 121 % 10 = 1, result = 0 * 10 + 1 = 1, temp = 121 / 10 = 12
    3. digit = 12 % 10 = 2, result = 1 * 10 + 2 = 12, temp = 12 / 10 = 1
    4. digit = 1 % 10 = 1, result = 12 * 10 + 1 = 121, temp = 1 / 10 = 0
    5. 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:
    1. Initial check: x is positive, so we proceed.
    2. Convert to string: str = "12321"
    3. Initialize: start = 0, end = 4
    4. Loop iterations:
      • Iteration 1: str[0] == str[4], start = 1, end = 3
      • Iteration 2: str[1] == str[3], start = 2, end = 2
    5. Loop ends (start is not < end)
    6. 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:

    1. Time Complexity: Both are O(log x) or O(n) where n is the number of digits.
    2. Space Complexity:
      • Approach 1: O(1), uses constant extra space.
      • Approach 2: O(log x) for string conversion.
    3. Readability: Approach 2 is generally more intuitive and easier to understand.
    4. 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

    Share

    Write your comment here !

    0 Responses