“Multiply two integers without using the multiplication operator.”
A few months ago I had a technical interview for a data science consulting firm. I was only asked one question, and it seemed so outlandishly removed from the job role that I wondered whether the interviewers had mistaken me for a candidate for another vacancy.
It was simply this:
“Write a function that multiplies two integers (positive or negative) without using the multiplication operator.”
The interviewers said they were fine with pseudocode.
I was sharing my screen on one of those snazzy online coding platforms. Within seconds, they said they wanted working code.
I chose to use Python – it was in the job requirements after all – and promptly wrote the most obvious code imaginable.
def multiply_by_summation(a, b):
result = 0
for _ in range(abs(b)):
result += a
return -result if b < 0 else resultThey asked whether I could optimise this, so I added a line to find the smaller of the two absolute values of a and b, and loop over the smaller one. I was asked to make it faster than O(|b|).
Then they seemed to get tired of the whole thing, and that was that.
I didn’t get the job.
The classic interview answer is of course so-called Russian peasant multiplication. It is huge misnomer. The method was used in Ancient Egypt, and why Russian peasant? Because of Vladimir Golenischev?
Anyway, here it is. The method relies on successive halving and doubling. It runs in O(log b) time.
def multiply_egyptian(a, b):
if a == 0 or b == 0:
return 0
# Make a positive, remember sign
negative = (a < 0) ^ (b < 0)
a, b = abs(a), abs(b)
result = 0
while b > 0:
if b & 1: # if b is odd
result += a
a <<= 1 # a = a * 2
b >>= 1 # b = b // 2
return -result if negative else resultAn even faster algorithm is Karatsuba multiplication, which should rightfully be called Russian multiplicaiton, since it was invented by the Russian Anatoly Karatsuba. This has a time complexity of O(n1.58n ), where n is the number of digits.
def add_n_times(base, times):
"""Add 'base' to itself 'times' times: base * times without '*'."""
result = 0
for _ in range(times):
result += base
return result
def pow10(n):
"""Compute 10**n using only addition (no '*', no '**')."""
if n == 0:
return 1
# Build iteratively: pow10(n) = pow10(n-1) * 10 = add pow10(n-1) ten times
result = 1
for _ in range(n):
result = add_n_times(result, 10) # result * 10
return result
def multiply_bit_only(a, b):
"""O(log n) multiplication using only bits/addition (for base case)."""
if a == 0 or b == 0:
return 0
negative = (a < 0) != (b < 0)
a, b = abs(a), abs(b)
result = 0
while b > 0:
if b & 1:
result += a
a <<= 1 # a *= 2 (bit shift allowed, as it's not '*')
b >>= 1 # b //= 2
return -result if negative else result
def karatsuba_no_multiply(x, y):
"""Full Karatsuba without any '*': recursive, O(n^1.58) asymptotically."""
# Base case: small numbers use bit multiplication
if abs(x) < 10 or abs(y) < 10:
return multiply_bit_only(x, y)
# Handle signs
negative = (x < 0) != (y < 0)
x, y = abs(x), abs(y)
if x < y:
x, y = y, x
# Digits in smaller number
n = len(str(y))
half = (n + 1) // 2 # Ceiling of n/2
# Split using div/mod
divider = pow10(half)
x_high = x // divider
x_low = x % divider
y_high = y // divider
y_low = y % divider
# 3 recursions instead of 4
z0 = karatsuba_no_multiply(x_low, y_low)
z2 = karatsuba_no_multiply(x_high, y_high)
z1 = karatsuba_no_multiply(x_low + x_high, y_low + y_high) - z2 - z0
# Combine without '*': use add_n_times for the "shifts" (powers of 10)
pow_half = divider # Already 10**half
pow_double = add_n_times(pow_half, pow_half) #
double_half = add_n_times(half, 2)
pow_double = pow10(double_half)
# Now "z2 * pow_double" = add z2, pow_double times
part_high = add_n_times(z2, pow_double)
# "z1 * pow_half" = add z1, pow_half times
part_mid = add_n_times(z1, pow_half)
# Total: part_high + part_mid + z0
result = part_high + part_mid + z0
return -result if negative else result
