freeCodeCamp Challenge Guide: Ethiopian multiplication

Ethiopian multiplication


Problem Explanation

Ethiopian multiplication is a method of multiplying integers using only addition, doubling, and halving. Implement the Ethiopian multiplication algorithm.


Solutions

Solution 1 (Click to Show/Hide)
function eth_mult(a, b) {
  // required functions
  const halve = (n) => Math.floor(n/2);
  const double = (n) => n + n;
  const isEven = (n) => n % 2 === 0;

  // setup variables
  let [left, right] = [a, b].sort((a, b) => a - b);
  let total = isEven(left) ? 0 : right;

  // Ethiopian algorithm
  while (left > 1) {
    left = halve(left);
    right = double(right);
    if (!isEven(left))
      total += right;
  }

  // return result
  return total;
}

Code Explanation

  • The halve(), double(), and isEven() functions are set up as required.
  • The code then iterates until the smaller (left) value is 1, adding the larger (right) value to the running total whenever the smaller (left) value is odd
Solution 2 (Click to Show/Hide)
const halve = (n) => Math.floor(n/2);
const double = (n) => n + n;
const isEven = (n) => n % 2 === 0;

function eth_mult(a, b) {
  return a > 1 ? (eth_mult(halve(a), double(b)) + (isEven(a) ? 0 : b)) : b;
}

Code Explanation

  • This solution uses recursion to accomplish the same logic as Solution 1