c++ 6ms solution without long type conversion


  • 0
    C

    Inspired by the solution from @jianchao.li.fighter,
    this solution avoids long type conversion during the calculation.

    class Solution {
    public:
    
        int divide(int dividend, int divisor) {
            
            /// Basic situations
            if (dividend == 0) return 0;
            
            if (divisor == 0) return numeric_limits<int>::max();
            else if (divisor == -1) {
                if (dividend == numeric_limits<int>::min()) return numeric_limits<int>::max();
                else return -dividend;
            }
            else if (divisor == 1) {
               return dividend;
            }
            
            /// Another specific situation
            if (divisor == numeric_limits<int>::min()) {
                return (dividend==numeric_limits<int>::min()) ? 1 : 0;
            }
            
            /// Figure out the sign of the quotient, and then convert dividend and divisor into negative values.
            int sign = 1;
            if ((dividend>0 && divisor<0) || (dividend<0 && divisor>0)) sign = -1;
            if (dividend > 0) dividend = -dividend;
            if (divisor > 0) divisor = -divisor;
            
            int res = 0;
            int dvd = dividend; /// Keep original "dividend" value
            while (dvd <= divisor) {
                /// Count AT MOST how many "divisors" could be accumulated to approach the current "dividend" from 
                /// upper-bound (now both dividend and divisor are negative values, so it is from upperbound)
                int accum = -divisor; int count = 1;
                while (   accum <= (numeric_limits<int>::max()>>1) /* The largest possible accumulation  */ 
                       && dvd <= -(accum << 1) /* Approach from upper bound */ ) {
                    accum = accum << 1;
                    count = count << 1;
                }
                dvd += accum; /// Update the dividend.
                res += count;
            }
            
            return sign * res;
        }
    };
    

Log in to reply
 

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