2
\$\begingroup\$

This code replaces each element in an array with the product of every other element in the array but the current element, without using division. So, for the array [5,2,3], the program outputs [6,18,108].

The code is below, but in essence, it iterates through each element, and sets the element to the product of the other elements.

So, for the array [5,2,3], it replaces the first element with the product of 2*3, so the array becomes [6,2,3]. Then it replaces the second element with the product of 6 and 3, so the array becomes [6,18,3]. Finally, it replaces the third element with the product of 6 and 18, so the array becomes [6,18,108].

Looking for general suggestions here, like how to improve the time complexity (someone suggested using some sort of different type of product or something but I don't know how to do that)

// productOfArray
// This function calculates the product of every value in the given array.
function productOfArray(array: number[])
{
    let product = 1;
    for (let x of array)
        product *= x; // should I be using *= or write product = product * x?
    return product;
}

// replaceWithProduct
// This function replaces each element in an array with the product of
// every other element in the array but the current element.
function replaceWithProduct(array: number[])
{
    for (let i=0; i<array.length; i++)
    {
        let arrayWithoutElement = array.slice(0,i).concat(array.slice(i+1,array.length));
        array[i] = productOfArray(arrayWithoutElement);
    }
    return array;
}

// Test the above functions.
let array = [5,2,3];
console.assert(productOfArray(array) === 30);
let newArray = replaceWithProduct(array);
let testArray = [6,18,108]; // This is what newArray should be.
for (let i=0; i<testArray.length; i++)
    console.assert(newArray[i] === testArray[i]);

console.log("Finished");
\$\endgroup\$
1
  • 5
    \$\begingroup\$ I'm not convinced that the result you are aiming for is the result that the "question" is aiming for. I'd expect [5, 2, 3] to be [6, 15, 10] by the description ... \$\endgroup\$
    – Vogel612
    Sep 28, 2021 at 23:38

3 Answers 3

3
\$\begingroup\$

The productOfArray could be implemented by reduce.

function productOfArray(array: number[]): number {
  return array.reduce((product, e) => product *= e, 1)
}

The reduce method could also be used to implement the replaceWithProduct function, if you reorganize the algorithm a bit.

function replaceWithProduct(source: number[]): number[] {
  return source.reduce(reducer, []);
}

function reducer(acc: number[], e: number, i: number, source: number[]): number[] {
  return acc.concat(productOfArray(acc) * productOfArray(source.slice(i + 1)));
}

It calculates a sprecific element by mulitplying the product of the already considered elements with all rest elements. This approach is only simpler, if you are familar with reduce, I guess.

To minimize the computations, you could cache and update the products instead of recalculating them in every reducer call.

function replaceWithProduct(source: number[]): number[] {
  return source.reduce(withReducer(source), []);
}

function withReducer(source: number[]): (acc: number[], e: number) => number[] {
  let lastAccProduct = 1;
  let lastRestProduct = productOfArray(source);

  return (acc: number[], e: number): number[] => {
    lastRestProduct /= e;
    const currentProduct = lastAccProduct * lastRestProduct;
    lastAccProduct *= currentProduct;
    return acc.concat(currentProduct);
  };
}

The example encapsulates the cache values within a High Order Function, which means, that withReducer is a function, which returns another function. If the concept is new to you, it's possibly hard to understand.


With the restriction of avoiding division, you need to compute the rest products by processing the array from right to left. Therefore you can use reduceRight. The complexity keeps the same as with last example.

function replaceWithProduct(source: number[]): number[] {
  return source.reduce(withReducer(source), []);
}

function withReducer(source: number[]): (acc: number[], e: number) => number[] {
  const restProducts = calculateRestProducts(source);
  let accProduct = 1;

  return (acc: number[], e: number): number[] => {
    const currentProduct = accProduct * restProducts.shift();
    accProduct *= currentProduct;
    return acc.concat(currentProduct);
  };
}

function calculateRestProducts(source: number[]): number[] {
  let lastRestProduct = 1;
  return source
    .slice(1)
    .reduceRight((acc, e) => acc.concat(lastRestProduct *= e), [1])
    .reverse();
}
\$\endgroup\$
4
  • \$\begingroup\$ Why wouldn't I need to recalculate the product? \$\endgroup\$
    – moonman239
    Sep 28, 2021 at 17:20
  • \$\begingroup\$ The code presented here is not well-behaved when the input array contains a 0 \$\endgroup\$
    – Vogel612
    Sep 28, 2021 at 23:39
  • \$\begingroup\$ That, and your code feels hacky. \$\endgroup\$
    – moonman239
    Sep 29, 2021 at 0:52
  • \$\begingroup\$ I guess, if you are familar with functional programming concepts, it's straighforward. The introduction of the cache variables reduces the complexity from n^2 to n, because the full recalculation of the product would consinder (n-1) elements, which isn't necessary with the cache variables lastAccProduct, lastRestProduct. Since there was nothing said about the zero handling, I didn't cover it. \$\endgroup\$
    – sschmeck
    Sep 29, 2021 at 8:23
2
\$\begingroup\$

Do you actually need to replace the result into the original array? That makes it unnecessarily complicated in my opinion (and is bad practice). Why not just return a new array?

The logic can also be simplified by just calculating the product of all numbers and then dividing that with each number in turn:

function productsOfOthers(numbers) {
  const product = numbers.reduce((product, e) => product * e, 1);
  return numbers.map(n => product / n);
}

And if you really need it to be the same array at the end, wrap it in a function that copies the result back:

function copyIntoArray(source, target) {
   source.forEach((n, i) => target[i] = n);

   // Could be left out, if you know/assume they are the same length,
   // as it is in this case
   if (target.length > source.length) {
      target.length = source.length;
   }
}

function replaceWithProduct(numbers) {
  const products = productsOfOthers(numbers);
  copyIntoArray(products, numbers);

  // Could just as well not return anything since you are reusing the array anyway
  return numbers;
}

This is the \$O(2n)\$ (or \$O(3n)\$ in case of the copying) = \$O(n)\$ instead of (i believe) \$O(n^2)\$ due to the repeated multiplication.

One draw back maybe a slight risk of overflow, however if the product of all numbers overflow, it's very likely that the product of all except one would overflow too anyway. Or use BigInt.


If zeros are allowed...

This makes it a bit more complicated, however one could write a product method, that counts the zeros and ignores them for the product:

function product(numbers) {
   return numbers.reduce(
     ({product, zeros}, n) => 
       n === 0 ? 
         {product, zeros: zeros + 1} :
         {product: product * n, zeros}, 
     {product: 1,  zeros: 0}
   );
}

And then build the result based on the number of zeros counted:

function productsOfOthers(numbers) {
  const {product, zeros} = product(numbers);
  switch (zeros) {
    case 0: 
      return numbers.map(n => product / n);
    case 1:
      return numbers.map(n => n === 0 ? product : 0)
    default:
      return Array(numbers.length).fill(0);
  }
}

When division isn't allowed

In this case I'd avoid all the expensive slicing and concatenating and write a product function that ignores a specific index:

function product(numbers, ignoreIndex) {
  return numbers.reduce(
    (product, n, index) => 
      index === ignoreIndex ? product : product * n, 
    1
  );
}

function productsOfOthers(numbers) {
  return numbers.map((_, index, array) => product(array, index));
}

And since I seem to be on a roll, here is a version that reuses the product of the first numbers. I moved away from functional programming, because I believe it would become too difficult to read in this case.

function productFromIndex(numbers, index) {
  let product = 1;
  for (let i = index; i < numbers.length; i++) {
    product *= numbers[i];
  }
  return product;
}

function productsOfOthers(numbers) {
  let previousProduct = 1;
  const result = [];
  for (let i = 0; i < numbers.length; i++) {
    result[i] = previousProduct * productFromIndex(numbers, i + 1);
    previousProduct *= numbers[i];
  }
  return result;
}
\$\endgroup\$
4
  • \$\begingroup\$ Forgot to mention: The original challenge does not allow division. \$\endgroup\$
    – moonman239
    Sep 28, 2021 at 22:43
  • \$\begingroup\$ This algorithm utterly fails if the array contains zeros. Even if you attempt to avoid dividing by zero, having two (or more) zeros in the array should give a result of all zeros. \$\endgroup\$
    – Vogel612
    Sep 28, 2021 at 23:28
  • \$\begingroup\$ @Vogel612 I've added some alternatives. \$\endgroup\$
    – RoToRa
    Sep 29, 2021 at 5:38
  • \$\begingroup\$ @moonman239 I've added some alternatives. \$\endgroup\$
    – RoToRa
    Sep 29, 2021 at 5:44
0
\$\begingroup\$

There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.

— C. A. R. Hoare

const productWithout = (arr: number[], idx: number) =>
  arr.reduce((acc, v, idx2) => (idx === idx2 ? acc : v * acc), 1);

const replaceIn = (arr: number[], idx: number, v: number) =>
  arr.map((r, idx2) => (idx === idx2 ? v : r));

const replaceWithProduct = (arr: number[]) =>
  arr.reduce(
    (acc, _, idx) => replaceIn(acc, idx, productWithout(acc, idx)),
    arr
  );
\$\endgroup\$

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.