Saturday, May 23, 2015

Palindrome Number

Problem Statement

Determine whether an integer is a palindrome. Do this without extra space.

Source: https://leetcode.com/problems/palindrome-number/
Programming Language: C#
Run Time Complexity: O(N)(Number of digits in the input)
Space Complexity: Constant space for divider


public bool IsPalindrome(int x)
{
    // Input validation -ve number is not palindrome number
    if (x < 0)    
        return false;    

    // Set divider to 1 
    int divider = 1;

    // While the number of digits in divider is eual to the number of digits of input
    while (x / divider >= 10)
    {
        divider *= 10;
    }

    // While input is not equal to 0
    while (x != 0)
    {
        // Take the right most digit
        int right = x % 10;

        // Take the left most digit
        int left = x / divider;
        
        // Not a palindrome number if left and right digit not match
        if (right != left)        
            return false;
        
        // input equal to mod of divider to get the number skipping left most digit
        x %= divider;
        
        // input divide by 10 to skip the right most digit
        x /= 10;
        
        // divider should be reduced by factor of 100 since right and left most digits are processed
        divider /= 100;
    }

    // Input validated and is palindrome number return true
    return true;
}

No comments:

Post a Comment