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;
}
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
}
}
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)) {
}
}
}
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
}
}
}
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
}
}
}
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;
}
Resources
Top comments (0)