Multiply Two Numbers without using multiplication,division, bitwise operators and loops

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

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

Example 2

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

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

C++

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

Go

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

Java

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

Python

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

C++

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

Go

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

Java

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

Python

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.