Implement multiplication without using the multiplication operator

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds.

Q: What role is this question designed for?

This question is commonly asked for Data Scientist candidates during technical 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?

PracHub · Accepted Answer

This question evaluates proficiency in bitwise arithmetic, integer overflow semantics, sign handling, and algorithmic efficiency for implementing multiplication without using multiplication or division operators.

Quick Overview

Implement multiplication without using the multiplication operator

Unchecked 32-bit Multiply Without *

Constraints

Examples

Hints

Saturating 32-bit Multiply Without *

Constraints

Examples

Hints