C++ accepted solution: divide and conquer (binary tree) w/ using only int type


  • 1
    S

    This solution is based on this equation:
    Let x be the dividend, k be the divisor, half = floor(x/2).
    Then we have:
    x/k = (half / k * 2) + (half % k * 2 + (x - half * 2)) / k

    Of course the multiplication, division and mod are implemented with bit shift, addition and subtraction.

    The recursion stack depth is at maximum 31, because int type is 32 bits and it's signed.

    I'd appreciate any suggestions and simplification ideas. Also please let me know if you find any extreme cases that can break this code. Thanks!

    class Solution
    {
    public:
    int divide(int dividend, int divisor) {
    	// deal with edge cases
    	if (dividend == 0) return 0;
    	if (divisor == 0) return INT_MAX;
    	if (dividend == divisor) return 1;
    	if (divisor == INT_MIN) return 0;
    	if (dividend == INT_MIN) {
    		if (divisor == 1) return INT_MIN;
    		if (divisor == -1) return INT_MAX;
    
    		// divide the INT_MIN in half so its absolute value won't overflow
    		int half = dividend >> 1;
    		int absHalf = abs(half);
    		int absDivisor = abs(divisor);
    		int result;
    		// if the divisor is greater than the half of INT_MIN, we know the result is 1 (or -1)
    		// this check is also necessary to prevent overflow from the later calculation of "halfRemainder << 1"
    		if (absHalf < absDivisor){
    			result = 1;
    		}
    		else{
    			int halfRemainder;
    			int remainder;
    			result = (recursiveDivide(absHalf, absDivisor, halfRemainder) << 1) + recursiveDivide(halfRemainder << 1, absDivisor, remainder);
    		}			
    		return divisor < 0 ? result : -result;
    	}
    	if (dividend == -divisor) return -1;
    	// done with edge cases
    	bool isNegative = (dividend > 0) ^ (divisor > 0);
    	int absDividend = abs(dividend);
    	int absDivisor = abs(divisor);
    	int result;
    	int remainder;
    	if (absDivisor == 1) result = absDividend;
    	else if (absDivisor == 2) result = absDividend >> 1;
    	else result = recursiveDivide(absDividend, absDivisor, remainder);
    	return isNegative ? -result : result;
    }
    
    int recursiveDivide(int dividend, int divisor, int& remainder){
    	if (dividend < divisor) {
    		remainder = dividend;
    		return 0;
    	}
    	else if (dividend == divisor){
    		remainder = 0;
    		return 1;
    	}
    	else if (dividend - divisor < divisor){ //cannot do comparison like "dividend < (divisor << 1)" cause it may overflow
    		remainder = dividend - divisor;
    		return 1;
    	}
    	else{
    		int half = dividend >> 1;
    		int halfRemainder;
    		return (recursiveDivide(half, divisor, halfRemainder) << 1) + recursiveDivide((halfRemainder << 1) + dividend - (half << 1), divisor, remainder);
    	}
    }
    

    };


Log in to reply
 

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