7
\$\begingroup\$

The problem is: loop through a list of numbers and for each one of them get the product of all the others and return a new array.

For example in [1,2,3,4,5] the third element should be 40 because 1 × 2 × 4 × 5 = 40

I'm looking for feedback on efficiency and good practices.

function main(numbers) {
    var result = [];
    for (var i in numbers) {
        var n = 1;
        for (var j in numbers) {
            if (i != j) {
                n *= numbers[j];
            }
        }
        result.push(n);
    }
    return result;
}

var a = [2, 6, 9, 31, 55];

console.log(main(a).toString());

\$\endgroup\$
  • \$\begingroup\$ Are you interested in a solution which keeps your chosen multiplication order iteratively from the first to the last index - or are the given answers sufficient? \$\endgroup\$ – le_m Apr 14 '17 at 15:46
7
\$\begingroup\$

What you have shown is an \$O(n^2)\$ solution in that you use nested loops to determine the results.

I would suggest an \$O(2n)\$ approach:

function main(numbers) {
    // one iteration to get product of whole array
    var arrayProduct = numbers.reduce(function(product, value) {
        return product * value;
    }, 1);

    // one iteration to map new array values by dividing 
    // full array product by current value
    return numbers.map(function(value) {
        return arrayProduct / value;
    });
}

You could probably use for loops instead of Array functions to micro-optimize this, but if I put myself into the position of someone who might grade such an algorithmic challenge as this. I would probably be happier to see code like this, as it still meets the requirement to optimize the performance to \$O(2n)\$, while providing code that is more readable. In other words, I would rather see the reduce() and map() calls in a production code base unless I had a use case where I really needed to squeeze every drop of performance out of this function.

ES6 version:

const main = (numbers) => {
    const arrayProduct = numbers.reduce( (product, value) => product * value, 1);
    return numbers.map( (value) => arrayProduct / value );
}

One could also easily foresee a case where larger arrays could easily hit up against the Number.MAX_SAFE_INTEGER value in javascript (\$2exp53\$), so one might consider throwing an error at some point to abort the operation.

const main = (numbers) => {
    const arrayProduct = numbers.reduce(
        (product, value) => {
            const product = product * value;
            if (product >= Number.MAX_SAFE_INTEGER) {
                throw new RangeError('Product has reached Number.MAX_SAFE_INTEGER');
            }
            return product;
        },
        1
    );
    return numbers.map( (value) => arrayProduct / value );
}
\$\endgroup\$
  • 3
    \$\begingroup\$ In-case you didn't know, on Code Review you can use MathJax for equations, and so allows you to write things like \$O(n)\$ and \$O(n^2)\$. The latter was made by typing \$O(n^2)\$. \$\endgroup\$ – Peilonrayz Apr 13 '17 at 21:44
  • \$\begingroup\$ @Peilonrayz Thanks. I know I had seen it before (and even had my posts edited as such previously), but didn't recall the shortcuts. \$\endgroup\$ – Mike Brant Apr 13 '17 at 21:51
  • 1
    \$\begingroup\$ Nice answer. Pretty minor but you can save one division by saving the the next to to last product. \$\endgroup\$ – paparazzo Apr 13 '17 at 22:04
  • 1
    \$\begingroup\$ @Paparazzi Indeed, though i would consider that more of a micro-optimization, and on that probably makes the code look less "clean". \$\endgroup\$ – Mike Brant Apr 13 '17 at 22:24
  • 6
    \$\begingroup\$ What if the array contains a zero? \$\endgroup\$ – Roland Illig Apr 14 '17 at 5:22
6
\$\begingroup\$

You can split your operation on the input array into a forward and backward pass. The forward pass assigns each resulting element the product of all preceding elements while the backward pass multiplies each resulting element with the product of all successors.

By doing so, you reduce the number of inner loop iterations and thus computational complexity from n² to n where n is the length of the input array:

function main(numbers) {
  let result = new Array(numbers.length);
  
  // Forward pass:
  let before = 1;
  for (let i = 0; i < numbers.length; ++i) {
    result[i] = before;
    before *= numbers[i];
  }

  // Backward pass:
  let after = 1;
  for (let i = numbers.length - 1; i >= 0; --i) {
    result[i] *= after;
    after *= numbers[i];
  }
  
  return result;
}

// Examples:
console.log(main([2, 6, 9, 31, 55]).join()); // 92070,30690,20460,5940,3348
console.log(main([1, 2, 3]).join());         // 6,3,2
console.log(main([0.7, 0.8]).join());        // 0.8,0.7

Implementation details:

  • This code avoids usage of in which can be problematic when the array prototype has been modified by third party code.

  • While the same function can be written recursively, non-recursive code bypasses possible call stack size limits and - in this case - is more expressive and thus more readable as well as more performant.

  • Also, while more declarative functional patterns such as map, reduce and forEach could be used, they all would require access to additional accumulator variables before and after defined outside their local callback scopes and make the forward-backward pass pattern less explicit and thus the code less readable.

  • Compared to the answer given by @kyrill and @MikeBrant, this implementation avoids division and is thus more robust. E.g. given [0.7, 0.8], this implementation computes [0.8, 0.7] while a division would introduce precision errors and result in [0.7999999999999999, 0.6999999999999998].

  • For some numbers a, b, c the result of a * b * c differs from c * b * a due to limited floating point precision and chaining of precision errors. Thus, this implementation doesn't faithfully reproduce the original implementation's results (due to the chosen multiplication order which I assume has been/can be chosen arbitrarily).

  • Some people prefer squeezing the before and after declaration into the loop initialization, which I would avoid for semantic reasons - they are accumulators and not loop counters.

  • Explicit initialization via result = new Array(numbers.length) is more readable than iterative calls to result.push() in the first pass. However, the later might give you a small performance boost in some engines for small arrays.

\$\endgroup\$
  • \$\begingroup\$ Why did you choose prefix operators when incrementing and decrementing? I played around with using prefix (as you did) compared with postfix and was able to achieve correct results in both cases. \$\endgroup\$ – Peter Aug 13 at 20:58
1
\$\begingroup\$

@RolandIllig has raised a fair point: If the array contains a zero, the result at the index of that zero will be NaN.

Here is a functional solution.

  • If the array contains multiple zeros, then all products will contain at least one zero, and therefore all products are zero.
  • If the array contains one zero, all products will be zero, except the one at the index of that zero.

const main2 = (numbers) => {
    const firstZeroIdx = numbers.indexOf(0);
    const secondZeroIdx = numbers.slice(firstZeroIdx+1).indexOf(0);
    const containsZero = firstZeroIdx !== -1;
    const containsMultipleZeros = secondZeroIdx !== -1;

    let res;    

    if (containsMultipleZeros) {
      res = numbers.map( _ => 0 );
    }
    else {
      const product = numbers.reduce((acc, val) => acc * (val || 1), 1);

      if (containsZero) {
        res = numbers.map( (val) => (val === 0) ? product : 0 );
      }
      else {
        res = numbers.map( (val) => product / val );
      }
    }

    return res;
};

This could be further "simplified". Ehm...

const main3 = (numbers) => {
    const product = numbers.reduce((acc, val) => acc * val, 1);
    const firstZeroIdx = numbers.indexOf(0);
    const productWithoutFirstZero = numbers.reduce(
              (acc, val, idx) => acc * (val || idx === firstZeroIdx), 1);
    return numbers.map(
              (val) => val ? (product / val) : productWithoutFirstZero );
};
\$\endgroup\$
0
\$\begingroup\$

A little bit late to the party, but here is an O(n) ES6 version of solving the problem only looping through the array a single time to achieve the desired results.

function multiplyArr(arr) {
    return arr.map((item) => eval(`${arr.join('*')}/${item}`));
}

The catch with this solution is that you can multiply all of the values of the array, but then divide by the current value to "remove" it. This method joins all the values of the array with a multiplication symbol and then divides by the current value. After that you eval the string to get the numeric result.

Note: Additional logic would be needed if 0 is in array

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! arr.filter() would also loop through the array so "only looping through the array a single time" isn't quite accurate... \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Jan 23 at 20:00
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ Updated it with a O(n) single loop. \$\endgroup\$ – SkyOut Jan 23 at 20:04
  • 1
    \$\begingroup\$ I would consider this use of eval() to be a nasty hack. \$\endgroup\$ – 200_success Jan 23 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.