Skip to content

08.05. Recursive Mulitply

Description

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.

Solutions

Solution 1: Recursion + Bit Manipulation

First, we check if \(B\) is \(1\). If it is, we directly return \(A\).

Otherwise, we check if \(B\) is an odd number. If it is, we can right shift \(B\) by one bit, then recursively call the function, and finally left shift the result by one bit and add \(A\). If not, we can right shift \(B\) by one bit, then recursively call the function, and finally left shift the result by one bit.

The time complexity is \(O(\log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the size of \(B\).

1
2
3
4
5
6
7
class Solution:
    def multiply(self, A: int, B: int) -> int:
        if B == 1:
            return A
        if B & 1:
            return (self.multiply(A, B >> 1) << 1) + A
        return self.multiply(A, B >> 1) << 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int multiply(int A, int B) {
        if (B == 1) {
            return A;
        }
        if ((B & 1) == 1) {
            return (multiply(A, B >> 1) << 1) + A;
        }
        return multiply(A, B >> 1) << 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int multiply(int A, int B) {
        if (B == 1) {
            return A;
        }
        if ((B & 1) == 1) {
            return (multiply(A, B >> 1) << 1) + A;
        }
        return multiply(A, B >> 1) << 1;
    }
};

1
2
3
4
5
6
7
8
9
func multiply(A int, B int) int {
    if B == 1 {
        return A
    }
    if B&1 == 1 {
        return (multiply(A, B>>1) << 1) + A
    }
    return multiply(A, B>>1) << 1
}

1
2
3
4
5
6
7
8
9
function multiply(A: number, B: number): number {
    if (B === 1) {
        return A;
    }
    if ((B & 1) === 1) {
        return (multiply(A, B >> 1) << 1) + A;
    }
    return multiply(A, B >> 1) << 1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
impl Solution {
    pub fn multiply(a: i32, b: i32) -> i32 {
        if b == 1 {
            return a;
        }
        if (b & 1) == 1 {
            return (Self::multiply(a, b >> 1) << 1) + a;
        }
        Self::multiply(a, b >> 1) << 1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    func multiply(_ A: Int, _ B: Int) -> Int {
        if B == 1 {
            return A
        }
        if (B & 1) == 1 {
            return (multiply(A, B >> 1) << 1) + A
        }
        return multiply(A, B >> 1) << 1
    }
}

Comments