Easy divide and conquer solution


  • 0
    A

    Logic is simple: suppose we are doing 15/2, since 2+2=4, and 4+4=8, we know 15=2x4+7, then we just have to know result of 7/2. Keep doing this until we reach 1/2.

    public class Solution {
        public int Divide(int dividend, int divisor) {
            if (divisor==0) { return int.MaxValue; }
            if (divisor==1) { return dividend; }
            if (divisor==-1) { return dividend==int.MinValue?int.MaxValue:-dividend; }
            bool isNeg = dividend<0 && divisor>0 || dividend>0 && divisor<0;
            long dd = Math.Abs((long)dividend);
            long dr = Math.Abs((long)divisor);
            long res = div(dd, dr);
            return isNeg?-(int)res:(int)res;
        }
        
        private long div(long dd, long dr){  // all positive
            if (dd<dr) { return 0; }
            long res = 1, pre = dr;
            while(dd-dr>=dr){
                dr += dr;
                res += res;
            }
            long final = div(dd-dr, pre) + res;
            return final;
        }
    }

Log in to reply
 

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