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:
- 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 |
|