DEV Community

Steven Frasica
Steven Frasica

Posted on

Algorithms: Product Sum from an Array

We'll be working on a problem today in which we get the product sum from an array that contains integers and other arrays also containing integers. This problem helped me understand recursion more, and hopefully it does the same for you.

Problem

This problem came from AlgoExpert.

We're tasked with writing a function that takes in a "special" array and returns the product sum.

The special array is non-empty and contains integers or other arrays. We can get the product sum of an array by adding all of its elements together and then multiplying by the level of depth of the array.

The depth is determined by how nested the array is.
Ex. The depth of [] is 1. The depth of the inner array in [[]] is 2. The depth of the innermost array in [[[]]] is 3.

In an array, [x, y], the product sum is (x + y). In array [x, [y, z]], the product sum is x + 2 * (y + z). In array [x, [y, [z]]], the product sum is x + 2 * (y + 3z).

Example Input:

[5, 2 [-7, 1], 3, [6, [-13, 8], 4]]

Example Output:

12

calculation:

5 + 2 + 2 * (7 - 1) + 3 + 2 * (6 + 3 * (-13 * 8) + 4)

Approach

We'll initialize a variable sum to keep track of our total sum as we add together integers in the array or in the nested arrays.

A for loop will be used to iterate through our main array to do work on each element. Our array's elements will consist of integers or arrays containing integers or arrays as well. That means we need to do different things whether we encounter arrays or integers while we loop.

When we encounter integers, we'll want to multiply those integers by the depth, and add it to the sum.

When we encounter an element that is an array, we want to recursively call the productSum function on that array, passing in that array and a multiplier increased by 1 as arguments. The reason we increase the multiplier by 1 is because if we encounter an array, that means it is nested, and is one level deeper than the previous array. This recursive call allows us to drill down into the nested arrays and access their integers to then multiply by the level of depth and add it to the total sum.

Solution

We have our given function with a default value of 1 for multiplier, which will increase as we access more nested arrays. We'll be returning sum as our final answer, but initially set it to 0.

function productSum(array, multiplier = 1) {
  let sum = 0;
}
Enter fullscreen mode Exit fullscreen mode

We write out our for loop to iterate through an array. We'll put code in the loop to run depending on whether we encounter an array or an integer.

function productSum(array, multiplier = 1) {
  let sum = 0;
  for (let element of array) {
  //do some work here
  }
}
Enter fullscreen mode Exit fullscreen mode

We use the Array.isArray() function to determine if the element is an array. It'll return true if it's an array, false if otherwise.

function productSum(array, multiplier = 1) {
  let sum = 0;
  for (let element of array) {
   if (Array.isArray(array)) {

   }
  }
}
Enter fullscreen mode Exit fullscreen mode

If our conditional returns true, we call the productSum function on our current element which is an array, pass in the element and the multiplier increased by 1, since the array is nested a level deeper. We also multiply the entire product sum by the multiplier to account for the depth. We add it to our total sum.

function productSum(array, multiplier = 1) {
  let sum = 0;
  for (let element of array) {
   if (Array.isArray(element)) {
     sum += productSum(element, multiplier + 1) * multiplier
   }
  }
}
Enter fullscreen mode Exit fullscreen mode

Otherwise, we multiply the current element by the level of depth its array is in and add it to the total sum.

function productSum(array, multiplier = 1) {
  let sum = 0;
  for (let element of array) {
   if (Array.isArray(element)) {
     sum += productSum(element, multiplier + 1) * multiplier
   } else {
     sum += element * multiplier
   }
  }
}
Enter fullscreen mode Exit fullscreen mode

Lastly, we make sure to return our total sum outside of the for loop.

function productSum(array, multiplier = 1) {
  let sum = 0;
  for (let element of array) {
   if (Array.isArray(element)) {
     sum += productSum(element, multiplier + 1) * multiplier
   } else {
     sum += element * multiplier
   }
  }
  return sum;
}
Enter fullscreen mode Exit fullscreen mode

Resources

-AlgoExpert

Discussion (0)