Summary of 3 C++ solutions


  • 18

    -1- log-based solution

       class Solution {
        public:
            int divide(int dividend, int divisor) {
                /** a/b = e^(ln(a))/e^(ln(b)) = e^(ln(a)-ln(b)) **/
                if(dividend==0)  return 0;
                if(divisor==0)  return INT_MAX;
                
                double t1=log(fabs(dividend));
                double t2=log(fabs(divisor));
                long long result=double(exp(t1-t2));
                if((dividend<0) ^ (divisor<0))  result=-result;
                if(result>INT_MAX)  result=INT_MAX;
                return result;
            }
        };
    

    -2- Binary Index tree idea inspired solution,

    as we can decompose any result number to sum of the power

    of 2.

    Here is the C++ implementation.

    class Solution {
    public:
        int divide(int dividend, int divisor) {
            if(!divisor || (dividend==INT_MIN && divisor==-1))   return INT_MAX;
            
            int sign=((dividend<0)^(divisor<0)) ? -1:1;
            long long m=labs(dividend);
            long long n=labs(divisor);
            int result=0;
            
            /** dvd >= 2^k1*dvs + 2^k2*dvs ... **/
            while(m>=n){
                long long temp=n, count=1;
                while(m >= (temp<<1)){
                    temp<<=1;
                    count<<=1;
                }
                m-=temp;
                result+=count;
            }
            
            return sign==1?result:-result;
        }
    };
    

    -3- concise version of the solution 2

    class Solution {
    public:
        int divide(int dividend, int divisor) {
            long long result=0;
            long long m=abs((long long)dividend);
            long long n=abs((long long)divisor);
            while(m>=n){
                long long s=n, power=1;
                while((s<<1) <= m) { s<<=1; power<<=1; }
                result+=power;
                m-=s;
            }
            
            if( (dividend>0) ^ (divisor>0))  result = -result;
            return result>INT_MAX ? INT_MAX:result;
        }
    };

  • 0

    Here is the implementation by myself.

    THe inner details are different as I use power to "++" .

    But the mistakes I made in the process includes:

            m-=(temp<<power);
            result+=std::pow(2,power);
    

    For the equation involves the bit operation and the power operation. We should add small bracket to

    deal with the priority problem as the priority is important if we mismade them. It can cause messy bugs.

    Here is the AC code:

    class Solution {
    public:
        int divide(int dividend, int divisor) {
            long long m, n, result=0;
            m=abs((long long)dividend);
            n=abs((long long)divisor);
            while(m>=n){
                long long temp=n, power=1;
                while((temp<<power) <= m){
                    power+=1;
                }
                power-=1;
                m-=(temp<<power);
                result+=std::pow(2,power);
            }
            if( (dividend>0) ^ (divisor>0))  result = -result;
            return result>INT_MAX ? INT_MAX:result;
        }
    };

  • 0
    P

    So the Time Complexity is O(logn) ?


Log in to reply
 

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