Cracking The Coding Interview Together – Problem 8.5: Recursive Multiply

Picture this: You are building a low-level arithmetic coprocessor or working within a strict embedded environment where hardware multiplication instructions are either disabled, heavily penalized, or outright unavailable. You are handed two positive integers and told to multiply them together. The catch? The asterisk operator (*) is strictly off-limits. How do you implement multiplication from scratch using only addition, subtraction, and bit shifting while keeping performance optimal?

This is the exact challenge we face in Problem 8.5 of Cracking the Coding Interview. At first glance, this looks like a trivial loop of repeated additions. But as senior engineers, we know that a naive O(n) approach will completely fall apart when scaled to large inputs. Today, we are going to break down this problem together, engineer an optimal recursive solution using bit manipulation, and build a production-ready implementation.

Problem Statement

Write a recursive function to multiply two positive integers without using the * operator. You are allowed to use addition, subtraction, and bit shifting. Furthermore, you should minimize the number of those operations.

Our operational goals are:

• Accept two positive integers, say a and b.
• Return their product without using the multiplication operator.
• Execute the operation recursively.
• Minimize operations to achieve logarithmic time complexity relative to the smaller number.

Analyze the Problem Together

Let's break down the constraints and find our "Aha!" conflict. If we rely on repeated addition—adding a to itself b times—our time complexity is O(b). If b is a 32-bit integer, that can take up to 4 billion operations in the worst-case scenario. That is unacceptable for high-throughput systems.

To minimize operations, we need to think like how computers multiply at the hardware level. Consider multiplying 12 * 7. We know that 7 can be broken down into binary components: 4 + 2 + 1 (or 111 in binary). Therefore, 12 * 7 = (12 * 4) + (12 * 2) + (12 * 1).

Even better, we can compute multiplications by powers of two using bit shifting. Shifting a number left by 1 is equivalent to multiplying by 2 (x << 1). Let's compare our approaches:

By always ensuring we split the smaller of the two numbers, we guarantee our recursion depth remains bounded by the logarithmic size of the smaller operand.

Questions for the Interviewer

Before writing a single line of code, a senior engineer establishes boundaries by asking clarifying questions:

• "Should we handle negative integers, or can we safely assume both inputs are strictly positive as stated in the prompt?"
• "What are the maximum bounds of the inputs? Do we need to account for integer overflow (exceeding 32-bit signed limits)?"
• "Is iterative recursion or tail-call optimization preferred, or is a standard recursive stack frame acceptable?"

Think About the Solution

Our architecture for this solution relies on a helper function that takes the smaller number as the multiplier. This ensures our time complexity is always O(log(min(a, b))):

1. Identify the smaller and larger of the two numbers to optimize recursion depth.
2. Base cases: If the multiplier is 0, return 0. If the multiplier is 1, return the other number.
3. Divide the multiplier by 2 using a right shift (smaller >> 1).
4. Recursively compute the product of the larger number and half of the smaller number.
5. Add the result to itself (which handles even numbers). If the multiplier was odd, add one extra instance of the larger number.

Write Code and Explain

Here is our production-ready Java implementation:

public class RecursiveMultiply {

    public static int multiply(int a, int b) {
        int smaller = a < b ? a : b;
        int bigger = a < b ? b : a;
        return minProductHelper(smaller, bigger);
    }

    private static int minProductHelper(int smaller, int bigger) {
        // Base cases
        if (smaller == 0) {
            return 0;
        }
        if (smaller == 1) {
            return bigger;
        }

        // Compute half by shifting right by 1 (equivalent to division by 2)
        int s = smaller >> 1;
        int halfProd = minProductHelper(s, bigger);

        // If smaller is even
        if (smaller % 2 == 0) {
            return halfProd + halfProd;
        } else {
            // If smaller is odd
            return halfProd + halfProd + bigger;
        }
    }

    public static void main(String[] args) {
        System.out.println("13 * 7 = " + multiply(13, 7)); // Expected: 91
        System.out.println("31 * 12 = "+ multiply(31, 12)); // Expected: 372
    }
}

Let's walk through the execution step-by-step with multiply(13, 7):

• smaller = 7, bigger = 13.
• We call minProductHelper(7, 13). 7 is odd. We compute s = 7 >> 1 = 3.
• We call minProductHelper(3, 13). 3 is odd. We compute s = 3 >> 1 = 1.
• We call minProductHelper(1, 13). Base case met! Returns 13.
• Back in minProductHelper(3, 13): halfProd = 13. Since 3 is odd, we return 13 + 13 + 13 = 39.
• Back in minProductHelper(7, 13): halfProd = 39. Since 7 is odd, we return 39 + 39 + 13 = 91.

Time & Space Complexity

Let's evaluate the performance of our algorithm:

• Time Complexity: O(log(s)), where s is the smaller of the two numbers. Because we divide the smaller number by 2 at each recursive step via bit shifting, the number of recursive calls scales logarithmically.
• Space Complexity: O(log(s)) for the call stack. The maximum depth of our recursion is proportional to the number of bits in the smaller integer.

Why This Problem Matters (The Senior Perspective)

At first glance, interview questions like Recursive Multiply feel like academic exercises. However, mastering bit manipulation and divide-and-conquer recursion forms the bedrock of systems programming, cryptography, and low-latency computing. Understanding how to break arithmetic down into bitwise operations gives you a deeper intuition for how CPUs process instructions, enabling you to write highly optimized code when working with hardware constraints or performance-critical data pipelines.

Final Thoughts

We've successfully designed an optimal, production-grade solution for recursive multiplication without relying on the arithmetic multiplication operator. Practice tracing the bit shifts on paper to build strong muscle memory for bitwise operations. Happy coding, and see you in the next breakdown!