# #2 Product Sum

###### tags:`Recursion` `Easy`

## Problem
Write a function that takes in a "special" array and returns its product sum.
A "special" array is a non-empty array that contains either integers or other "special" arrays. The product sum of a "special" array is the sum of its elements, where "special" arrays inside it are summed themselves and then multiplied by their level of depth.
The depth of a "special" array is how far nested it is. For instance, the depth of `[]` is `1`; the depth of the inner array in `[[]]` is `2`; the depth of the innermost array in `[[[]]]` is `3`.
Therefore, the product sum of `[x, y]` is `x + y`; the product sum of `[x, [y, z]]` is `x + 2 * (y + z);` the product sum of `[x, [y, [z]]]` is `x + 2 * (y + 3z)`.

### Sample Input

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

### Sample Output

12 // calculated as: 5 + 2 + 2 * (7 - 1) + 3 + 2 * (6 + 3 * (-13 + 8) + 4)

<br>

:::spoiler **Optimal Space & Time Complexity**

O(n) time | O(d) space - where n is the total number of elements in the array, including sub-elements, and d is the greatest depth of "special" arrays in the array

:::

<br>

:::spoiler Hint 1
Try using recursion to solve this problem.
:::

<br>

:::spoiler Hint 2
Initialize the product sum of the "special" array to 0. Then, iterate through all of the array's elements; if you come across a number, add it to the product sum; if you come across another "special" array, recursively call the productSum function on it and add the returned value to the product sum. How will you handle multiplying the product sums at a given level of depth?
:::

<br>

:::spoiler Hint 3
Have the productSum function take in a second parameter: the multiplier, initialized to 1. Whenever you recursively call the productSum function, pass in the multiplier incremented by 1.
:::

<br>

<hr/>

## Solutions

### Official

// O(n) time | O(d) space - where n is the total number of elements in the array,
// including sub-elements, and d is the greatest depth of "special" arrays in the array
function productSum(array, multiplier = 1) {
  let sum = 0;
  for (const element of array) {
    if (Array.isArray(element)) {
      sum += productSum(element, multiplier + 1);
    } else {
      sum += element;
    }
  }
  return sum * multiplier;
}

<br>

---

### Everyone's

#### global variable
:::spoiler 東

// Time O(n) | Space O(c); 
// where n is amount of intergers in input array, c is the greatest depth of input array 

let depth = 1;
function productSum(array) {
  let sum = 0;
  for(const item of array){
    if(Array.isArray(item)){
      depth ++;
      sum += depth * productSum(item);
    } else {
      sum += item;
    }
  }
  depth = 1;
  return sum;
}

:::

<br>

#### a new function
:::spoiler YC

/*
 * time: O(n) - where n is the total number of elements in the array (including the element in “special” array)
 * space: O(d) - where d is the greatest depth of “special” array's  
*/
function productSum(array) {
  const doSum = (arr, depth = 1) => {
    let sum = 0;
    for(const val of arr){
      if(Array.isArray(val)){
        sum += doSum(val, depth + 1);
      }else{
        sum += val;
      }
    }
    return sum * depth;
  }
  return doSum(array, 1);
}

:::
<br>

:::spoiler Hao

/**
 * Time complexity: O(N) and space complexity: O(M) which
 * N is the total number of elements in the array including sub-elements and
 * M is the greatest depth among the invocation of function.
 */

function productSum(array) {
  const getArraySum = (array, weight) => {
    return array.reduce((acc, value) => {
      const sum = Array.isArray(value) ? getArraySum(value, weight + 1) : value;
      return acc + sum * weight;
    }, 0);
  };
  return getArraySum(array, 1);
}

:::

<br>

#### add additional parameters to function
:::spoiler 月

function productSum(array, depth = 1) {
  // Time O(n) Space O(n)
  const sum = array.reduce((a,b) => {
    if(Array.isArray(b)) return a + productSum(b, depth + 1);
    return a + b;
  }, 0)
  return depth * sum 
}

:::

<br>

### backlog

:::spoiler Raiy

:::

<br>

:::spoiler Becky

:::

<br>

---

## Supplement / Discussion
1. global variable
2. repeat itself
- a new function (if needed)
- add additional parameters to function (if needed)