C++ Solution, beats 45% of submissions


  • 0
    B

    Algorithm runs in O(n) time. It will take n-iterations to find the NULL pointer at the end of string value. It will take floor(n/2) iterations to reverse the integers in-place. The algorithm then implements a str.compare() to verify that the reversed string does not overflow a 32-bit integer.

    This algorithm is O(n) run-time and uses O(1) space.

    class Solution {
    public:
        int reverse(int x) {
            // convert int to string
            string value = to_string(x);
            
            char *headPtr = &value[0];
            char *tailPtr = head;
            // find the last digit of the value
            while(*tailPtr!=NULL)
                tailPtr++;
            tailPtr--;
            // skip the '-' character in the value
            bool neg = value[0] == '-'?true:false;
            if(neg)
                headPtr++;
    
            // reverse the string in-place
            while(headPtr<tailPtr){
                char t = *headPtr;
                *headPtr = *tailPtr;
                *tailPtr = t;
                headPtr++;
                tailPtr--;
            }
            // check for 32-bit int overflow of reversed string
            if(neg && value.size()>10 && overflow(value))
                return 0;
            else if (!neg && value.size()>9 && overflow(value))
                return 0;
            
            // convert string value to int and return
            int out = atoi(value.c_str());
            return out;
        }
        bool overflow(string x)
        {
            bool neg = x[0]=='-'?true:false;
            // max 32-bit int is (2^32) -1
            int max = pow(2,31)-1;
            string value = to_string(max);
            
            if(neg)
            {
                if(x.compare(1,x.size()-1,value) > 0)
                    return true;
                else
                    return false;
            }
            else
            {
                if(x.compare(value) > 0)
                    return true;
                else
                    return false;
            }
        }
    };
    

Log in to reply
 

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