DEV Community

Prashant Mishra
Prashant Mishra

Posted on • Originally published at youtube.com

Divide two integers without using division or multiplication operators

Problem

Tc : (log2N)2(log_2N) ^ 2
Sc: O(1)

class Solution {
    public int divide(int dividend, int divisor) {
        //edges cases
        if(dividend == divisor) return 1;

        boolean positive = true;
        if(dividend <=0 && divisor >0) positive = false;
        else if(dividend >=0 && divisor <0) positive = false;

        long n = dividend;
        long d = divisor;

        n = Math.abs(n);
        d = Math.abs(d);
        long quotient = 0;

         while (n >= d) {
            int count = 0;
            while (n >= (d << (count + 1))) {
                count++;
            }

            n -= (d << count);
            quotient += (1 << count);
        }
        if(quotient == (1<<31) && positive) return Integer.MAX_VALUE;
        else if(quotient ==(1<<31) && !positive) return Integer.MIN_VALUE;
        return (int)( positive ? quotient: -quotient);

    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)