Comment on page

29.Divide-Two-Integers

29. Divide Two Integers
题目地址
​https://leetcode.com/problems/divide-two-integers/​
题目描述
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, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.
​
Example 1:
​
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.
​
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -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.
代码
Approach #1 Repeated Subtraction
public int divide(int dividend, int divisor) {
    //Reduce the problem to positive long integer to make it easier.
    //Use long to avoid integer overflow cases.
    int sign = 1;
    if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0))
        sign = -1;
    long ldividend = Math.abs((long) dividend);
    long ldivisor = Math.abs((long) divisor);
​
    //Take care the edge cases.
    if (ldivisor == 0) return Integer.MAX_VALUE;
    if ((ldividend == 0) || (ldividend < ldivisor))    return 0;
​
    long lans = ldivide(ldividend, ldivisor);
​
    int ans;
    if (lans > Integer.MAX_VALUE){ //Handle overflow.
        ans = (sign == 1)? Integer.MAX_VALUE : Integer.MIN_VALUE;
    } else {
        ans = (int) (sign * lans);
    }
    return ans;
}
​
private long ldivide(long ldividend, long ldivisor) {
    // Recursion exit condition
    if (ldividend < ldivisor) return 0;
​
    //  Find the largest multiple so that (divisor * multiple <= dividend), 
    //  whereas we are moving with stride 1, 2, 4, 8, 16...2^n for performance reason.
    //  Think this as a binary search.
    long sum = ldivisor;
    long multiple = 1;
    while ((sum+sum) <= ldividend) {
        sum += sum;
        multiple += multiple;
    }
    //Look for additional value for the multiple from the reminder (dividend - sum) recursively.
    return multiple + ldivide(ldividend - sum, ldivisor); // 4 + 2 + 1
}
Approach #2
This solution has O(logN^2) time complexity.
public int divide(int A, int B) {
  if (A == 1 << 31 && B == -1) {
    return (1 << 31) - 1;
  }
  int a = Math.abs(A), b = Math.abs(B);
  int res = 0, x = 0;
  while (a - b >= 0) {
    for (x = 0; a - (b << x << 1) >= 0; x++);
​
    res += 1 << x;
    a -= b << x;
  }
​
  return (A > 0) == (B > 0) ? res: -res;
}

287.Find-the-Duplicate-Number

299.Bulls-and-Cows

Last modified 2yr ago