Multiplication Without Multiplication Operators

A problem I learned about from the book Cracking The Coding Interview is how to multiply two numbers without using multiplication and division operators. I decided to write down what I learned from the solution since I find it to be a fascinating solution.

Naive Approach

The most straightforward method involves repeatedly adding the multiplicand by the value of the multiplier (e.g., for 3 * 5, it would be calculated as 5 + 5 + 5). However, while this naive approach is conceptually simple, it is not the most efficient solution, as it necessitates the use of the addition operator multiple times. In exploring more optimized strategies, we aim to minimize the frequency of addition operations and enhance computational efficiency.

Divide and Conquer

To minimize the use of addition operations, we use a divide-and-conquer approach. Calculating half of the multiplication and then doubling the result (e.g., 4 * 5 = (2 * 5 + 2 * 5)) becomes the key strategy. This involves dividing the smaller half successively until reaching one or zero. For each division, we calculate the multiplication by dividing the smallest multiplicand in half and doubling the result.

function minProduct(a, b) {
    let bigger = a < b ? b : a;
    let smaller = a < b ? a : b;
    return minProductHelper(smaller, bigger);
}

function minProductHelper(smaller, bigger) {
    if (smaller === 0) {
        return 0;
    } else if (smaller === 1) {
        return bigger;
    }

    let s = smaller >> 1; // Divide by 2
    let side1 = minProductHelper(s, bigger);
    let side2 = side1;

    if (smaller % 2 === 1) {
        side2 = minProductHelper(smaller - s, bigger);
    }

    return side1 + side2;
}

This technique will only work if the result of half of the multiplication is an even number. If it's an odd number, we will do the same thing we did for the first half. We divide it until we reach zero or one and then double it.

In conclusion, the divide-and-conquer technique provides a fascinating solution to multiply two numbers efficiently without using multiplication and division operators. It shows the beauty of algorithmic thinking and helps to explore unconventional computational strategies.