Topic link

Leetcode-cn.com/problems/di…

Train of thought

In fact, the essence of a divisor is subtraction, that is, how many divisor does the dividend contain. So we can just roughly cycle through the divisor until the dividend is less than the divisor. The pseudocode is as follows:

While dividend < divisor cnt++ dividend -= divisorCopy the code

However, there may be inefficient and timeout problems every time we subtract the divisor, so let’s think about whether we can subtract the divisor in ascending order, subtract 1 divisor first, then subtract 2 divisor,… And so on. At the same time, our results should also be added 1, 2, etc. The pseudocode is as follows:

While dividend < multiple divisor + multiple divisor CNT += CNT multiple divisor += multiple divisorCopy the code

The following is an example:

31/8 =3 First loop: Dividend :31 Divisor :8 Multiple divisor :8 CNT :1 31 < 16 Satisfies loop conditions CNT = 2 Multiple divisor =32 Second loop: Dividend: 31-2 * 8 = 15 Divisor :8 Multiple divisor :8 CNT :1 15 < 18 Does not meet the cycle conditions CNT = 1 Third cycle: Dividend: 15-1 * 8 = 7 Divisor :8 Because the dividend < divisor, return 0. The final result is 2 + 1 = 3Copy the code

code

Go

func divide(dividend int, divisor int) int {
	if dividend == 0 {
		return 0
	}
	if divisor == 1{
		return dividend
	}
	if divisor == - 1 {
		if dividend == math.MinInt32 {
			return math.MaxInt32
		}
		return -dividend
	}
	var flag int
	if (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0) {
		flag = 1
	} else {
		flag = - 1
	}

	dividend = abs(dividend)
	divisor = abs(divisor)

	return flag * div(dividend, divisor)
}

func abs(num int) int {
	if num >= 0 {
		return num
	}
	return -num
}

func div(dividend int, divisor int) int  {
	if dividend < divisor {
		return 0
	}
    res := 1
	mulDivisor := divisor
	for dividend > mulDivisor + mulDivisor {
		res += res
		mulDivisor += mulDivisor
	}
	return res + div(dividend - res * divisor, divisor)
}
Copy the code