Divide Two Integers
Question: 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: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
You may view the full question here.
Approach 1: As usual, let’s start with something straight forward and naive. Multiplication is repeated addition. From this we can arrive at the following code —
//Approach 1:
//RunTime: Time Limit Exceeded
//Memory usage: N/Aclass Solution {
public int divide(int dividendI, int divisorI) {
int sign = 1;
int signD = 1;
double dividend = dividendI;
double divisor = divisorI;
if(divisor<0){
sign = -1;
divisor*=-1;
}
if(dividend<0){
signD = -1;
dividend*=-1;
}
int q = 0;
if(divisor==1){
double result = dividend*sign*signD;
if(result>Integer.MAX_VALUE || result<Integer.MIN_VALUE){
return Integer.MAX_VALUE;
}
return (int)result;
}
while(dividend>=divisor){
dividend-=divisor;
q++;
}
return q*sign*signD;
}
}
Clearly, we have a long way to go.
Approach 2: After a few hours of toil, we got better . Back at school, remember the way we did long division. The following code, does exactly that for us —
//Approach 2:
//Runtime: 1ms
//Memory usage: 32.5MBclass Solution {
public int divide(int dividend, int divisorI) {
int signDs = getSign(divisorI);
int signDd = getSign(dividend);
double divisor = (double)divisorI * signDs;
double q = 0;
double rem = 0;
char[] chars = String.valueOf(dividend).toCharArray();
for(char c : chars){
if(c=='-'){
continue;
}
rem = rem * 10 + (c - '0');
int tempQ = 0;
while(rem>=divisor){
tempQ++;
rem-=divisor;
}
q=q*10 + tempQ;
}
if(q*signDs*signDd > Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}
return (int)(q*signDs*signDd);
}
private int getSign(int num){
if(num<0){
return -1;
}
return 1;
}
}
Find more posts here.
Cheers & Chao!