Problem

Compute the product a * b given two integers a and b without using the multiplication (*), division (/), bitwise operators, or explicit loops. You may use recursion and addition or other allowed mathematical identities.

Examples

Example 1

1
2

Input: a = 6, b = 4
Output: 24

Example 2

1
2

Input: a = -3, b = 5
Output: -15
Similar Problems

Solution

Method 1 — Recursive repeated addition

Intuition

Multiplication is repeated addition: a * b equals adding a to itself |b| times. If loops are not allowed, recursion performs the same repeated-step behaviour implicitly via the call stack.

Approach

  1. Handle base case: if b == 0 return 0.
  2. If b > 0, return a + multiply(a, b - 1).
  3. If b < 0, return -multiply(a, -b) (preserve sign).

Edge cases:

  • Very large |b| will cause deep recursion and may overflow the call stack.

Code

1
2
3
4
5
6
7
8
9

class Solution {
 public:
  // non-static public method
  int multiply(int a, int b) {
    if (b == 0) return 0;
    if (b > 0) return a + multiply(a, b - 1);
    return -multiply(a, -b);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

package main

type Solution struct{}

// Multiply is a public method on Solution
func (s Solution) Multiply(a, b int) int {
  if b == 0 { return 0 }
  if b > 0 { return a + s.Multiply(a, b-1) }
  return -s.Multiply(a, -b)
}
1
2
3
4
5
6
7

class Solution {
  public int multiply(int a, int b) {
    if (b == 0) return 0;
    if (b > 0) return a + multiply(a, b - 1);
    return -multiply(a, -b);
  }
}
1
2
3
4
5
6
7

class Solution:
  def multiply(self, a: int, b: int) -> int:
    if b == 0:
      return 0
    if b > 0:
      return a + self.multiply(a, b - 1)
    return -self.multiply(a, -b)

Complexity

  • ⏰ Time complexity: O(|b|), one recursive call per unit of |b|.
  • 🧺 Space complexity: O(|b|) due to recursion depth.

Method 2 — Algebraic identity + recursive halving (use math)

Intuition

Use the identity (a + b)^2 = a^2 + b^2 + 2ab to express ab = ((a+b)^2 - a^2 - b^2) / 2. If direct division is not allowed, compute division by two using a recursive divide_by_2 that subtracts 2 repeatedly.

Approach

  1. Compute val = (a + b)^2 - a^2 - b^2. Then ab = val / 2.
  2. Implement divide_by_2(n) recursively by subtracting 2 until n < 2; count how many times.
  3. Use sign handling to allow negative values of val.

Edge cases: the identity relies on correct squaring and careful handling of large integers; using recursion to divide may be slow and depth-heavy.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
 public:
  int divideBy2(int n) {
    if (n < 2) return 0;
    return 1 + divideBy2(n - 2);
  }

  // non-static public multiply
  int multiply(int a, int b) {
    int whole = (a + b) * (a + b);
    int aa = a * a;
    int bb = b * b;
    int val = whole - aa - bb;
    if (val >= 0) return divideBy2(val);
    return -divideBy2(-val);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

package main

type Solution struct{}

func (s Solution) divideBy2(n int) int {
  if n < 2 { return 0 }
  return 1 + s.divideBy2(n-2)
}

func (s Solution) Multiply(a, b int) int {
  whole := (a + b) * (a + b)
  aa := a * a
  bb := b * b
  val := whole - aa - bb
  if val >= 0 { return s.divideBy2(val) }
  return -s.divideBy2(-val)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
  int divideBy2(int n) {
    if (n < 2) return 0;
    return 1 + divideBy2(n - 2);
  }

  public int multiply(int a, int b) {
    int whole = (a + b) * (a + b);
    int aa = a * a;
    int bb = b * b;
    int val = whole - aa - bb;
    if (val >= 0) return divideBy2(val);
    return -divideBy2(-val);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
  def divide_by_2(self, n: int) -> int:
    if n < 2:
      return 0
    return 1 + self.divide_by_2(n - 2)

  def multiply(self, a: int, b: int) -> int:
    whole = (a + b) * (a + b)
    aa = a * a
    bb = b * b
    val = whole - aa - bb
    if val >= 0:
      return self.divide_by_2(val)
    return -self.divide_by_2(-val)

Complexity

  • ⏰ Time complexity: O(1) arithmetic for squaring plus O(val/2) for the recursive division step, so effectively O(|a*b|) in the worst case.
  • 🧺 Space complexity: O(val/2) for recursion depth in divide_by_2.