Simple O((log N) ^ 2) C++ solution


  • 53
    L

    Long division in binary:
    The outer loop reduces n by at least half each iteration. So It has O(log N) iterations.
    The inner loop has at most log N iterations.
    So the overall complexity is O(( log N)^2)

    typedef long long ll;
    
    int divide(int n_, int d_) {
        ll ans=0;
        ll n=abs((ll)n_);
        ll d=abs((ll)d_);
        while(n>=d){
            ll a=d;
            ll m=1;
            while((a<<1) < n){a<<=1;m<<=1;}
            ans+=m;
            n-=a;
        }
        if((n_<0&&d_>=0)||(n_>=0&&d_<0))
            return -ans;
        return ans;
    }

  • 1
    M

    Great solution! FYI, another minor final "ans" check is needed for the newly added {-2147483648, -1} test case. We need to return max int of 2147483647 for that test case.


  • 0
    Z

    what if d_ is 0?


  • 0
    L

    Your question is moot as the problem does not state what answer to provide when the divisor is zero. (Last i have seen it)


  • 0
    L

    @melvin are you serious we have to return int max for that test case? It is mathematically incorrect


  • 0
    M

    @lucastan: Yes, that's just a minor new test case for this problem at the author's discretion. (Even though it's mathematically incorrect, it can never be correct since 2147483648 can't be expressed in int. Your solution would return -2147483648, which is the standard result of division.)

    Here's your solution's submission result in this OJ:

    Submission Result: Wrong Answer More Details

    Input: -2147483648, -1
    Output: -2147483648
    Expected: 2147483647


  • 0
    N
    This post is deleted!

  • 19
    N

    When Input: -2147483648, -1

    the solution of @lucastan's will return wrong answer,

    Output: -2147483648

    Expected: 2147483647

    I modified the code for handling the case of overflow.


    int divide(int dividend, int divisor) {
        /******* handling the case of overflow *******/
        if(divisor == 1)
            return dividend;
        if(dividend == INT_MIN && abs(divisor) == 1)
            return INT_MAX;
        /*********************************************/
    
        int sign = (dividend > 0 ^ divisor > 0) ? -1 : 1;
    
        long ans = 0;
        long end = abs((long)dividend);
        long sor = abs((long)divisor);
    
        while(end >= sor) {
            long temp  = sor;
            long power = 1;
            while((temp << 1) < end) {
                power <<= 1;
                temp  <<= 1;
            }
            ans += power;
            end -= temp;
        }
        return sign * ans;
    }

  • 0
    C

    Just two suggestions: long is large enough for this case and with limits.h use INT_MAX and INT_MIN for clarity.


  • 0
    N

    Thanks for your suggestions : )


  • 0
    B

    no multiplication allowed...


  • 0
    C

    It just to determine the sign, not a major part of the calculation. It could be easily replaced with something like: return (dividend > 0 ^ divisor > 0) ? -ans: ans ;


  • 1
    H

    Below is code for log(n)

    class Solution {
    public:
    int divide(int dividend, int divisor) {
         long long p=dividend,q=divisor,m=1,a,ans=0;
         int f=0;
         
         if(p<0^q<0) f=1;        if(p<0) p=-p;          if(q<0) q=-q;
         if(p==q) if(f==1) return -1; else return 1;
         a=q;
         
        while(a<=p) {a=a<<1;m=m<<1;}  a=a>>1;m=m>>1;
    
        while(p>=q && p>0)
        {
          if(p>=a)
            { 
                p=p-a;
                ans=ans+m;   
            }      
            a=a>>1;m=m>>1;
        }
    
        if(f==1) {return -ans;} 
        
        else{if(ans==1+long(INT_MAX)) return INT_MAX; else return ans;} 
    }
      };

  • 0
    M

    Thanks for the last answer from hiren2. I think it's kind like greedy method and the time complexity is O(logN). If i'm wrong, hopes someone can figure it out. Write a simple version. C++ 8ms.

    int divide(int dividend, int divisor) { //O(logN)
        if(divisor==1) return dividend;
        if(divisor==0 || (dividend == INT_MIN && divisor == -1)) return INT_MAX;
        long dvd = abs((long)dividend), delta = abs((long)divisor), tims = 1, ans = 0;
        while(dvd >= delta) {
            tims <<= 1;
            delta <<= 1; //delta=tims*divisor
        }
        while( dvd>0 && delta>0) {
            while(dvd < delta) {
                tims >>= 1;
                delta >>= 1;
            }
            ans += tims;
            dvd -= delta;
        }
        return (dividend>0)^(divisor>0) ? -ans : ans; //XOR^
    }

  • 0
    Z

    if ((dividend > 0) ^ (divisor > 0)) {
    return -ans < Integer.MIN_VALUE ? Integer.MIN_VALUE : (int) -ans;
    } else {
    return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
    }


  • 0
    C

    In an asymptotic sense, O((logN)^2) is as fast as O(N). (You can prove by L'Hôpital's rule)

    But I do think O((logN)^2) is not the tight upper bound for your algorithm.

    Correct me if I am wrong.


  • 1

    @czxttkl said in Simple O((log N) ^ 2) C++ solution:

    In an asymptotic sense, O((logN)^2) is as fast as O(N).

    No.


  • 0
    C

    @StefanPochmann Thanks for pointing that out. I calculated wrong derivative when applying L'Hôpital's rule.


  • 0
    M

    Your sulution didn't consider the overflow situation.


Log in to reply
 

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