Implement multiplication without using the multiplication operator

Q: Implement multiplication without using the multiplication operator

This is a Coding & Algorithms interview question from Other for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Implement int multiply(int a, int b) without using * or /. You may use +, −, bitwise operators, and shifts. Requirements:

Handle negatives, zero, and the corner case INT_MIN * −1.
Achieve O(log |b|) additions via shift‑and‑add (Russian peasant), not naive O(|b|) repeated addition.
Assume 32‑bit signed ints. First implement unchecked overflow (two’s‑complement wrap), then a safe version that saturates to INT_MAX/INT_MIN on overflow without using 64‑bit types.
Analyze time and space complexity and prove correctness for all sign combinations.
Provide unit tests: 0×x, 1×x, −1×x, powers of two, random pairs, INT_MAX×2, INT_MIN×2, INT_MIN×−1. Follow‑ups: how would you extend to big integers and compare with Karatsuba? What changes if the platform lacks arithmetic right shift?

Implement multiplication without using the multiplication operator

Comments (0)