原文链接: https://leetcode-cn.com/problems/recursive-mulitply-lcci

英文原文

Write a recursive function to multiply two positive integers without using the * operator. You can use addition, subtraction, and bit shifting, but you should minimize the number of those operations.

Example 1:

 Input: A = 1, B = 10
 Output: 10

Example 2:

 Input: A = 3, B = 4
 Output: 12

Note:

1. The result will not overflow.

中文题目

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例1:

 输入：A = 1, B = 10
 输出：10

示例2:

 输入：A = 3, B = 4
 输出：12

提示:

1. 保证乘法范围不会溢出

通过代码

高赞题解

思路

1. 首先，求得A和B的最小值和最大值;
2. 然后，可以对其中的最小值当做乘数（为什么选最小值，因为选最小值当乘数，可以算的少），将其拆分成2的幂的和，即$min = a_0 * 2^0 + a_1 * 2^1 + … + a_i * 2^i + …$ ，其中$a_i$取0或者1。其实就是用二进制的视角去看待min，比如12用二进制表示就是1100，即1000+0100。举个例子，13 * 12 = 13 * (8 + 4) = 13 * 8 + 13 * 4 = (13 << 3) + (13 << 2); 具体详见如下代码：

public int multiply(int A, int B) {
    int min = Math.min(A, B);
    int max = Math.max(A, B);
    int ans = 0;

    for (int i = 0; min != 0; i++) {
        if ((min & 1) == 1) {
            ans += max << i;
        }
        min >>= 1;
    }

    return ans;
}

复杂度分析

• 时间复杂度：$O(logn)$，$n$不会超过$65536$。
• 空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
23298	34370	67.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言