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