Solution 1: Repeated Addition (Simple)
function multiply(a, b) {
// Handle zero
if (a === 0 || b === 0) return 0;
// Handle negative (make b positive for simplicity)
let negative = false;
if (b < 0) {
b = -b;
negative = !negative;
}
if (a < 0) {
a = -a;
negative = !negative;
}
let result = 0;
for (let i = 0; i < b; i++) {
result += a;
}
return negative ? -result : result;
}
console.log(multiply(3, 4)); // 12
console.log(multiply(-3, 4)); // -12
console.log(multiply(-3, -4)); // 12
console.log(multiply(7, 0)); // 0
Solution 2: Bit Manipulation (Efficient)
function multiplyBits(a, b) {
// Handle zero
if (a === 0 || b === 0) return 0;
// Handle negative
let negative = false;
if (a < 0) {
a = -a;
negative = !negative;
}
if (b < 0) {
b = -b;
negative = !negative;
}
let result = 0;
// Process each bit of b
while (b > 0) {
// If current bit is 1, add current a to result
if (b & 1) {
result += a;
}
// Double a (left shift)
a <<= 1;
// Halve b (right shift)
b >>= 1;
}
return negative ? -result : result;
}
console.log(multiplyBits(3, 5)); // 15
console.log(multiplyBits(17, 8)); // 136
console.log(multiplyBits(-6, 7)); // -42
How Bit Method Works
Example: 3 × 5 (5 = 101₂)
b = 5 = 101₂
Bit 0 (1): result += 3 × 2⁰ = 3
Bit 1 (0): skip
Bit 2 (1): result += 3 × 2² = 12
Total: 3 + 12 = 15 ✓
Step-by-step trace:
Initial: a=3, b=5, result=0
Iteration 1:
b & 1 = 1 → result += 3 = 3
a <<= 1 → a = 6
b >>= 1 → b = 2
Iteration 2:
b & 1 = 0 → skip
a <<= 1 → a = 12
b >>= 1 → b = 1
Iteration 3:
b & 1 = 1 → result += 12 = 15
a <<= 1 → a = 24
b >>= 1 → b = 0
Result: 15 ✓
Solution 3: Recursive
function multiplyRecursive(a, b) {
// Base cases
if (b === 0) return 0;
if (b === 1) return a;
// Handle negative
if (b < 0) return -multiplyRecursive(a, -b);
// If b is even: a * b = 2 * (a * b/2)
if (b % 2 === 0) {
return multiplyRecursive(a + a, Math.floor(b / 2));
}
// If b is odd: a * b = a + a * (b-1)
return a + multiplyRecursive(a, b - 1);
}
console.log(multiplyRecursive(4, 6)); // 24
console.log(multiplyRecursive(7, 9)); // 63
Complexity Comparison
| Method |
Time |
Space |
Notes |
| Repeated Addition |
O(b) |
O(1) |
Simple but slow |
| Bit Manipulation |
O(log b) |
O(1) |
Best approach |
| Recursive |
O(log b) |
O(log b) |
Call stack space |
Handling Large Numbers
In languages with fixed-size integers, overflow is possible:
function multiplySafe(a, b) {
const MAX_INT = 2147483647;
// Check for potential overflow
if (a !== 0 && Math.abs(b) > MAX_INT / Math.abs(a)) {
throw new Error("Overflow detected");
}
return multiplyBits(a, b);
}
Follow-Up: Division Without Division
My Amazon interviewer followed with: "Now implement division without / operator."
function divide(dividend, divisor) {
if (divisor === 0) throw new Error("Division by zero");
let negative = (dividend < 0) !== (divisor < 0);
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
let quotient = 0;
while (dividend >= divisor) {
dividend -= divisor;
quotient++;
}
return negative ? -quotient : quotient;
}
console.log(divide(10, 3)); // 3
console.log(divide(-10, 3)); // -3
Pro tip: These "without operator X" problems test your understanding of what operations really do at the bit level.
Related Problems
