8.5 Recursive Multiply

NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊

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

The easiest approach is to add each number one by one. We can choose the smallest number out of 2 arguments - and add the other number to it, one number at a time:

function multiply(a,b) {
  const max = Math.max(a,b);
  const min = Math.min(a,b);
  function recursiveMultiply(number, multiplier) {
    return (
      multiplier === 1 ? 
      number : 
      number + recursiveMultiply(number, multiplier - 1)
    )
  }
  return recursiveMultiply(max, min);
}

This algorithm uses addition n times, where n is the smallest of 2 arguments of multiplication function. Also the time complexity of this algorithm is O(n): we need to do something n times. Can we do better than that? The task requires to use the minimal amount of additions - and the time complexity can probably be improved as well 🤔

The second approach that I took seems to be a bit more optimal indeed. Similarly as in the previous case, I consider the bigger argument to be multiplicand (let's call it m), and the smaller one - multiplier (n). But in addition to this, I also create an array of pre-calculated values, in which I fill in only the indices that represent the power of 2. For instance, for m = 9 and n = 7 the array will look like this:

Each index in this array actually equals a multiplier of m: eg a number at index 4 would actually be m * 4 (or, in other words, (m + m) + (m + m)). We can do that with log₂n operations: each time we will be doubling the array length and the max number.

Note that we're stopping when the index * 2 <= n, and there's a reason for that. The sum of (some of the) numbers in this array will be used to get to the final result (9 * 7, in our example). We're stopping at the index 4, which means the max number we'll calculate for the array would be 9 * 4. If we would go on and calculate the next number as well, the next number would be 9 * 4 + 9 * 4 = 9 * 8 - which would exceed the 9 * 7 that we need to calculate at the end (9 * 8 can not one of the numbers that sum up to 9 * 7).

The next thing to do is to actually (recursively) use these pre-calculated numbers, and that is what recursiveMultiply() function does in the code below:

function multiply(a,b) {
  const max = Math.max(a,b);
  const min = Math.min(a,b);
  let values = [, max]
  let index = 1;

  //Fill in array of values for all indices = 2^n 
  while (index * 2 <= min) {
    const newIndex = index * 2;  
    values[newIndex] = values[index] + values[index];
    index = newIndex;
  } 

  // Recursively add the numbers from the array of values
  function recursiveMultiply(number, multiplier, valuesArray){
    if (multiplier === 0) { return 0; }
    const multLog = Math.log2(multiplier);
    const closestMaxIndex = Math.pow(2, Math.floor(multLog));
    const rest = recursiveMultiply(number, multiplier - closestMaxIndex, valuesArray);
    return valuesArray[closestMaxIndex] + rest;
  }

  return recursiveMultiply(max, min, values);
}

For 9 * 7, we would start with index 7 (the value of n) and search for the closest number that would be a power of 2 (smaller or equal to 7). 7 is not a power of 2, so we need to go down until 4. This chunk does exactly that:

const factorLog = Math.log2(factor);
const closestMaxIndex = Math.pow(2, Math.floor(factorLog));

Finally, we take the number from the pre-calculated array that is stored under closestMaxIndex index (index 4 in this case) - and sum up this number with the rest that still needs to be calculated. So, if we needed to calculate 9 * 7, and 9 * 4 is already known, the rest to be calculated is 9 * 3 : index 3 will be an argument of next iteration of recursiveMultiply. With the next recursive steps we will get 9 * 2 and 9 * 1 - and those numbers will sum up exactly to the result that we need to reach: (9 * 4) + (9 * 2) + (9 * 1) = 9 * 7.

When looking at complexity, this alternative solution uses only 2 * log₂n sums - and has a O(log₂n) time complexity 🙌 The bigger the argument get, the more benefit will this approach bring.