Recursive Java Solution 2ms


  • 1

    Keep substracting divisor and double it each time.

    public int divide(int a, int b) {
        if(a==Integer.MIN_VALUE){
            if(b==-1) return Integer.MAX_VALUE;
        }
        
        long x = a < 0 ? -(long)a : (long)a;
        long y = b < 0 ? -(long)b : (long)b;
        
        int res = recurse(x, y, 1);
        if(a < 0 && b < 0) return res;
        if(a < 0 || b < 0) return -res;
        return res;
    }
    
    public int recurse(long x, long y, int count) {
        if(x <= 0 || count==0) return 0;
        if(y > x) return recurse(x, y >>> 1, count >>> 1); //overshot, so divide and try again.
        else return recurse(x-y, y+y, count+count)+count;
    }

  • 1

    Whenever you overshoot and divisor goes more than dividend, go back to previous value, and try again.


Log in to reply
 

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