29. Divide Two Integers

Problem

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.

Problem Summary

Given two integers, the dividend dividend and the divisor divisor. Divide the two numbers, requiring that multiplication, division, and the mod operator are not used. Return the quotient obtained by dividing the dividend dividend by the divisor divisor.

Notes:

Both dividend and divisor are 32-bit signed integers.
The divisor is not 0.
Assume our environment can only store 32-bit signed integers, whose value range is [−2^31, 2^31 − 1]. In this problem, if the division result overflows, return 2^31 − 1.

Solution Ideas

Given the divisor and dividend, compute the quotient after division. Note that the value range is within [−2^31, 2^31 − 1]. Anything exceeding the range is calculated according to the boundary.
This problem can be solved with binary search. To find the quotient after division, take the quotient as the target to search for. The quotient's value range is [0, dividend], so search from 0 to the dividend. Use binary search: when (quotient + 1 ) * divisor > dividend and quotient * divisor ≤ dividend, or when (quotient+1)* divisor ≥ dividend and quotient * divisor < dividend, the quotient has been found; otherwise continue binary searching. Finally, pay attention to the sign and the Int32 value range specified by the problem.
3 points that are often written incorrectly in binary search:
1. low ≤ high (note that the exit condition of the binary search loop is less than or equal to)
2. mid = low + (high-low)>>1 (prevent overflow)
3. low = mid + 1 ; high = mid - 1 (pay attention to updating the values of low and high; if the update is incorrect, it will cause an infinite loop)

Code


package leetcode

import (
	"math"
)

// Solution 1: recursive binary search
func divide(dividend int, divisor int) int {
	sign, res := -1, 0
	// low, high := 0, abs(dividend)
	if dividend == 0 {
		return 0
	}
	if divisor == 1 {
		return dividend
	}
	if dividend == math.MinInt32 && divisor == -1 {
		return math.MaxInt32
	}
	if dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0 {
		sign = 1
	}
	if dividend > math.MaxInt32 {
		dividend = math.MaxInt32
	}
	// If changing recursion to non-recursion, it can be changed to the following code
	// for low <= high {
	// 	quotient := low + (high-low)>>1
	// 	if ((quotient+1)*abs(divisor) > abs(dividend) && quotient*abs(divisor) <= abs(dividend)) || ((quotient+1)*abs(divisor) >= abs(dividend) && quotient*abs(divisor) < abs(dividend)) {
	// 		if (quotient+1)*abs(divisor) == abs(dividend) {
	// 			res = quotient + 1
	// 			break
	// 		}
	// 		res = quotient
	// 		break
	// 	}
	// 	if (quotient+1)*abs(divisor) > abs(dividend) && quotient*abs(divisor) > abs(dividend) {
	// 		high = quotient - 1
	// 	}
	// 	if (quotient+1)*abs(divisor) < abs(dividend) && quotient*abs(divisor) < abs(dividend) {
	// 		low = quotient + 1
	// 	}
	// }
	res = binarySearchQuotient(0, abs(dividend), abs(divisor), abs(dividend))
	if res > math.MaxInt32 {
		return sign * math.MaxInt32
	}
	if res < math.MinInt32 {
		return sign * math.MinInt32
	}
	return sign * res
}

func binarySearchQuotient(low, high, val, dividend int) int {
	quotient := low + (high-low)>>1
	if ((quotient+1)*val > dividend && quotient*val <= dividend) || ((quotient+1)*val >= dividend && quotient*val < dividend) {
		if (quotient+1)*val == dividend {
			return quotient + 1
		}
		return quotient
	}
	if (quotient+1)*val > dividend && quotient*val > dividend {
		return binarySearchQuotient(low, quotient-1, val, dividend)
	}
	if (quotient+1)*val < dividend && quotient*val < dividend {
		return binarySearchQuotient(quotient+1, high, val, dividend)
	}
	return 0
}

// Solution 2: non-recursive binary search
func divide1(divided int, divisor int) int {
	if divided == math.MinInt32 && divisor == -1 {
		return math.MaxInt32
	}
	result := 0
	sign := -1
	if divided > 0 && divisor > 0 || divided < 0 && divisor < 0 {
		sign = 1
	}
	dvd, dvs := abs(divided), abs(divisor)
	for dvd >= dvs {
		temp := dvs
		m := 1
		for temp<<1 <= dvd {
			temp <<= 1
			m <<= 1
		}
		dvd -= temp
		result += m
	}
	return sign * result
}