Daily Coding Challenge 2

Given an array of numbers, return whether any two sums to K. For example, given [10, 15, 3, 7] and K of 17, return true since 10 + 7 is 17.

Follow Up:

Do the same problem without division

Solution 1

const arr = [1, 2, 3, 4, 5];

const product = arr.reduce((p, c) => p * c, 1);

console.log(arr.map(x => product / x));

Runtime O(n)

Follow Up Solution 1

function allButNProduct(arr) {
  const leftPartials = arr.slice();
  const rightPartials = arr.slice();

  arr.forEach((x, i) => {
    if (i === 0) {
      return;
    }
    leftPartials[i] = x * leftPartials[i - 1];
  })

  arr.forEach((x, i) => {
    const j = arr.length - 1 - i;
    if (i === 0) {
      return;
    }
    rightPartials[j] = arr[j] * rightPartials[j+1]
  });

  return arr.map((x, i) => {
    const left = leftPartials[i-1] || 1;
    const right = rightPartials[i+1] || 1;
    return left * right;
  });
}

Runtime O(n)

Follow Up Solution 2

This is much the same as the first one, but it removes 3 of the loops over the array. This amounts to nothing in terms of big-o complexity, but does reduce the constant. I suspect it would still be slower because of the large number of array resizes needed.

function allButNProduct(arr) {
  const leftPartials = [];
  const rightPartials = [];

  arr.forEach((x, i) => {
    const j = arr.length - 1 - i;
    if (i === 0) {
      leftPartials.push(x);
      rightPartials.unshift(arr[j]);
    } else {
      leftPartials.push(x * leftPartials[i - 1]);
      rightPartials.unshift(arr[j] * rightPartials[0]);
    }
  })

  return arr.map((x, i) => {
    const left = leftPartials[i - 1] || 1;
    const right = rightPartials[i + 1] || 1;
    return left * right;
  });
}

Follow Up Solution 3

This is a compromise between follow up 1 and 2. It merges two of the loops together, but removes the array resizes.

function allButNProduct(arr) {
  const leftPartials = arr.slice();
  const rightPartials = arr.slice();

  arr.forEach((x, i) => {
    const j = arr.length - 1 - i;
    if (i === 0) {
      return;
    } else {
      leftPartials[i] = x * leftPartials[i - 1];
      rightPartials[j] = arr[j] * rightPartials[j + 1];
    }
  })

  return arr.map((x, i) => {
    const left = leftPartials[i - 1] || 1;
    const right = rightPartials[i + 1] || 1;
    return left * right;
  });
}