Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.
The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.
Return the quotient after dividingdividendbydivisor.
Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For this problem, if the quotient is strictly greater than2^31 - 1, then return 2^31 - 1, and if the quotient is strictly less than-2^31, then return -2^31.
classSolution {
public:int divide(int dividend, int divisor) {
if (divisor ==0) throw std::invalid_argument("divisor is zero");
longlong a = std::llabs((longlong)dividend);
longlong b = std::llabs((longlong)divisor);
longlong ans =0;
while (a >= b) {
a -= b;
++ans;
}
int sign = ((dividend <0) ^ (divisor <0)) ?-1:1;
return (int)(sign * ans);
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
packagemainimport"errors"typeSolutionstruct{}
func (s*Solution) divide(dividend, divisorint64) (int64, error) {
ifdivisor==0 { return0, errors.New("divisor is zero") }
a:=dividendifa < 0 { a = -a }
b:=divisorifb < 0 { b = -b }
varansint64fora>=b {
a-=bans++ }
if (dividend < 0) != (divisor < 0) { ans = -ans }
returnans, nil}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution {
publicintdivide(int dividend, int divisor) {
if (divisor == 0) thrownew ArithmeticException("divisor is zero");
long a = Math.abs((long) dividend);
long b = Math.abs((long) divisor);
long ans = 0;
while (a >= b) {
a -= b;
++ans;
}
int sign = ((dividend < 0) ^ (divisor < 0)) ?-1 : 1;
return (int) (sign * ans);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution {
fundivide(dividend: Int, divisor: Int): Int {
if (divisor ==0) throw ArithmeticException("divisor is zero")
var a = kotlin.math.abs(dividend.toLong())
var b = kotlin.math.abs(divisor.toLong())
var ans = 0Lwhile (a >= b) {
a -= b
ans++ }
val sign = if ((dividend < 0) xor (divisor < 0)) -1else1return (sign * ans).toInt()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution:
defdivide(self, dividend: int, divisor: int) -> int:
if divisor ==0:
raiseZeroDivisionError('divisor is zero')
a = abs(dividend)
b = abs(divisor)
ans =0while a >= b:
a -= b
ans +=1if (dividend <0) ^ (divisor <0):
ans =-ans
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pubstructSolution;
impl Solution {
pubfndivide(&self, dividend: i64, divisor: i64) -> i64 {
if divisor ==0 { panic!("divisor is zero") }
letmut a = dividend.abs();
let b = divisor.abs();
letmut ans =0i64;
while a >= b {
a -= b;
ans +=1;
}
if (dividend <0) ^ (divisor <0) { -ans } else { ans }
}
}
We need to find the quotient given the divisor and dividend.
Any number can be represented in binary form:
1
num = a_0*2^0+ a_1*2^1+ a_2*2^2+...+ a_n*2^n
Same goes for quotient . Let us have an example: 58/5:
58 = (11) * 5 + 3
In binary, this quotient is ( $(11)_{10} = (1011)_2$ ):
1
2
58=(2^3+2^1+2^0)*5+3// --- (I)
58=[(2^3*5)+(2^1*5)+(2^0*5)]+3// --- (II)
We are given the equation 58 = q * 5 + rem and need to find q.
First, multiply 5 by powers of 2 until the result exceeds the dividend. Since multiplication operator is not allowed, we use bitwise left shift for multiplication:
1
2
3
4
5
5<<0=5// less than dividend
5<<1=10// less than dividend
5<<2=20// less than dividend
5<<3=40// less than dividend
5<<4=5*2*2*2*2=80// exceeds divided, so stop and consider previous value
We observe that:
1
58=(2^3*5)+(something *5)+ rem // --- (III)
You can see we are getting close to the equation we initialy wanted (eqa II).
Since 5 is multiplied by (2^3), we add (2^3) to our answer and update the dividend:
1
58-(2^3*5)=18= something *5+ rem
Further operating on equation III:
1
2
3
4
58 - (2^3 * 5) = (something * 5) + rem
58 - (8 * 5) = something * 5 + rem
58 - 40 = something * 5 + rem
18 = something * 5 + rem
What we effectively have done is, subtracted the result we got from our first step from dividend (58 - 40).
We arived at the same question again but with a smaller dividend this time.
dividend = 18, divisor = 5
Therefore let us repeat the process:
1
2
3
5 << 0 = 5 // less than dividend
5 << 1 = 5*2 = 10 // less than dividend
5 << 2 = 5*2*2 = 20 // exceeds divided, so stop and consider previous value
You can notice we are gradually advancing towards equ II:
Our new dividend is now:
1
2
3
4
18 - (2^1 * 5) = (something * 5) + rem
18 - (2 * 5) = something * 5 + rem
18 - 10 = something * 5 + rem
8 = something * 5 + rem
dividend = 8, divisor = 5
Repeating the process:
1
2
5 << 0 = 5 // less than dividend
5 << 1 = 5*2 = 10 // exceeds divided, so stop and consider previous value
We add 2^0 to our answer.
New dividend:
1
2
3
8 = (2^0 * 5) + (something * 5) + rem
8 - 5 = something * 5 + rem
3 = something * 5 + rem
dividend = 3, divisor = 5
At this step, we stop iterating as our dividend is less than the divisor (we have also found our remainder = 3, as 5 should be multiplied with 0 and what remains is the remainder).