This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Topic describes

This is 29 on LeetCode. Two numbers divided, medium difficulty.

Tag: “math”, “dichotomy”

Given two integers, dividend and divisor.

Dividing two numbers requires no multiplication, division, and mod operators.

Returns the quotient of dividend divided by divisor.

The result of integer division should truncate the decimal part, for example, TRUNCate (8.345) = 8 and TRUNCate (-2.7335) = -2

 

Example 1:

Input: Dividend = 10, Divisor = 3 Output: 3 Interpretation: 10/3 = TRUNCate (3.33333..) = truncate(3) = 3Copy the code

Example 2:

Input: Dividend = 7, Divisor = -3 Output: -2 Explanation: 7/-3 = TRUNCate (-2.33333..) = 2 -Copy the code

Tip:

  • Both dividend and divisor are 32-bit signed integers.
  • The divisor is not 0.
  • Assume that our environment can store only 32-bit signed integers with values in the range [− 2312^{31}231, 2312^{31}231 − 1]. In this case, if the division result overflows, 2312^{31}231 − 1 is returned.

Fundamental analysis

The main ambiguity lies in the third restriction “Assume that our environment can store only 323232-bit signed integers, whose numeric values range from [−231,231−1][−2^{31}, 2^{31} −1][− 231,231−1]. In this case, 231−12^{31} − 1231−1 is returned if the division result overflows.

This limitation can be understood in two ways:

  1. There is no restriction on algorithm uselong, just to explain why when overflow, return
    2 31 – 1 2 ^ {31} – 1     ;
  2. Limit algorithm uselong.

The original solution is here.

Understanding one (without limitationlong)

When long is not restricted, the basic idea is:

  • First of all,dividend 和 divisorThere are both “positive” and “negative” possibilities. If and only if one of them is negative, the result is negative. For convenience, we can first record the positive and negative signs of the final result, and then convertdividend 和 divisorTreat them as positive numbers;
  • Now both are satisfied
    x > = 0 x >= 0     And then usedividend 和 divisorAre allintAnd you can determine that the absolute value of the answer falls at
    [ 0 . d i v i d e n d ] [0, dividend]     Range (if and only ifdivisorIs in the range
    [ 0 . 1 ] [0, 1]     The answer is greater thandividend);
  • Suppose the answer is
    x x     , so in the
    x x     Is on the integer number line of the segmentation point, has “duality”, so we can find the segmentation point dichotomously:

    • The number yyy greater than XXX satisfies y∗b> AY * b>ay ∗b>a;
    • Y ∗b<=ay * b<=ay ∗b<= A;
  • According to the dichotomous analysis, we find dichotomouscheckThe implementation needs to use multiplication, so we need to implement a “no multiplication sign” implementation of multiplication (this can be done using the idea of multiplication)mulOperation).

Code:

class Solution {
    int INF = Integer.MAX_VALUE;
    public int divide(int _a, int _b) {
        long a = _a, b = _b;
        boolean flag = false;
        if ((a < 0 && b > 0) || (a > 0 && b < 0)) flag = true;
        if (a < 0) a = -a;
        if (b < 0) b = -b;
        long l = 0, r = a;
        while (l < r) {
            long mid = l + r + 1 >> 1;
            if (mul(mid, b) <= a) l = mid;
            else r = mid - 1;
        }
        r = flag ? -r : r;
        if (r > INF || r < -INF - 1) return INF;
        return (int)r;
    }
    long mul(long a, long k) {
        long ans = 0;
        while (k > 0) {
            if ((k & 1) = =1) ans += a;
            k >>= 1;
            a += a;
        }
        returnans; }}Copy the code
  • Time complexity: binary operation in the range of [0,a][0, a][0,a], complexity is O(log⁡a)O(\log{a})O(loga); The complexity of multiplication is O(log⁡b)O(\log{b})O(logb), which is related to the binary length of operands. The overall complexity of O (log ⁡ a ∗ log ⁡ b) O (\ log \ {a} * log {b}) O (loga ∗ logb)
  • Space complexity: O(1)O(1)O(1)

Understanding two (limitationlong)

Instead of using long all the way, we need to map all numbers to negative numbers for processing (with 000 as the cut-off point, negative numbers represent a larger range).

The basic idea is as follows:

  • At first, the boundary case is analyzed.
  • Record the sign of the final result and map both numbers to negative numbers;
  • Multipliers can be preprocessed or incrementeddividendCome close todivisorThe way.

Since all operands are negative, an overflow occurs if the operands are less than half of INT_MIN (-1073741824) during the self-multiplication process.

Code:

class Solution {
    int MIN = Integer.MIN_VALUE, MAX = Integer.MAX_VALUE;
    int LIMIT = -1073741824; // half of MIN
    public int divide(int a, int b) {
        if (a == MIN && b == -1) return MAX;
        boolean flag = false;
        if ((a > 0 && b < 0) || (a < 0 && b > 0)) flag = true;
        if (a > 0) a = -a;
        if (b > 0) b = -b;
        int ans = 0;
        while (a <= b){
            int c = b, d = -1;
            while (c >= LIMIT && d >= LIMIT && c >= a - c){
                c += c; d += d;
            }
            a -= c;
            ans += d;
        }
        returnflag ? ans : -ans; }}Copy the code
  • Time complexity: O (log ⁡ a ∗ log ⁡ b) O (\ \ log log {a} * {b}) O (loga ∗ logb)
  • Space complexity: O(1)O(1)O(1)

The last

This is the 29th article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions in LeetCode as of the start date, some of which have locks. We will finish all the questions without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.