Question

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$.

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

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;
  }
}

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;
  }
};

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
}

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;
}

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