An accepted solution using no extra 'variable'


  • 4
    W

    Yes I misunderstood the meaning of 'no extra space' and I took it for no extra local variable.
    Nevertheless I post a messy one here for those who are by any chance interested.
    I know it's not what the author intended and it is quite inefficient because of all the repetitive formulas but the basic approach is simple and clear so please don't vote me down :)

    #include <math.h>
    
    //number of digits of x
    #define n_digit_of(x) ((int)log10(x))
    
    //10^n
    #define ten_to_power_of(n) ((int)exp(log(10) * (n)))
    
    //e.g. the 'order' of 1221 is 1000
    #define order_of(x) (ten_to_power_of(n_digit_of(x)))
    
    //e.g. the number of 'front' 0s of 3000458 is 3.
    #define n_front_zero_of(x) (n_digit_of(x) - n_digit_of((x) % order_of(x)) - 1)
    
    
    bool isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
       
        while (x >= 10) {
            //compare the most significant and least significant digits
            if (x / order_of(x) != (x % 10)) {
                return false;
            }
            
            //in case like 400303004, we have to judge more digits
            if (n_digit_of(x) - n_digit_of(x % order_of(x)) > 1) {
                if (x % ten_to_power_of(n_front_zero_of(x) + 1) != (x % 10)) {
                    return false;
                }
            }
    
            //now strip the most significant and least significant parts and continue
            //e.g. 400303004 => 303        
            x = x % order_of(x) / ten_to_power_of((n_front_zero_of(x) + 1));
         }
        
        return true;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.