29. Divide Two Integers

LeetCode 29. Divide Two Integers

Description

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.

Tags

Math, Binary Search

Solution

首先根据被除数和除数的符号得到结果的符号，并将二者变成正数。然后进入循环，条件是dividend >= divisor。循环内初始化变量acc = divisor，然后将其不断翻倍直至它刚好大于等于被除数，与此同时用变量mul记录它翻了几倍，再将acc从被除数减去并把mul累加到结果上。循环结束后，先恢复结果的符号再判断其是否溢出。最后返回结果。

We first obtain the sign of result based on the signs of dividend and divisor, and turn them to be positive. Then we enter a loop which condition is dividend >= divisor. In the loop, we initialize acc = divisor and double it until it is just larger than or exactly equal to the dividend. Meanwhile, we use a new variable mul to record how many times it has become. Then we subtract acc from dividend and add mul to the result. After this loop, we recover the sign of the result and check if it overflows.

Complexity

• Time complexity: $O((log(n))^2)$

• Space complexity: $O(1)$

Code

func divide(dividend int, divisor int) int {
	ans, sign := 0, 1
	if dividend < 0 {
		dividend, sign = -dividend, -sign
	}
	if divisor < 0 {
		divisor, sign = -divisor, -sign
	}
	// e.g. 1023 / 1 = 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1
	for dividend >= divisor {
		// accumulated divisor, times of the original divisor
		acc, mul := divisor, 1
		for acc<<1 <= dividend {
			acc <<= 1
			mul <<= 1
		}
		ans += mul
		dividend -= acc
	}
	if sign == -1 {
		ans = -ans
	}
	if ans > 2147483647 || ans < -2147483648 {
		return 2147483647
	}
	return ans
}

Reference

1. https://leetcode-cn.com/problems/divide-two-integers/solution/29-python3-li-yong-er-jin-zhi-sou-suo-de-si-xiang-/