Product Sum - Interviewbit

Product Sum

Understanding the problem

We are given a "special" array, which contains integers and optionally other "special" arrays. We are asked to write a function that is going to return the sum of the elements in the "special" array. If the element is a "special" array, we need to sum up the elements in the "special" array and then multiply the sum by the depth of the "special" array. For instance, if the input array is [3, [4, 5]], then the result should be 3 + 2 * (4 + 5) = 21; if the input array is [6, [4, [5]]], then the result should be 6 + 2 * (4 + 3 * 5) = 44.

Approach

One might notice that the "special" array has a recursive structure. Therefore, the problem can be solved recursively.

We are going to have a recursive function which takes in a "special" array and the depth of the "special" array as arguments. The depth of the initial input array is going to be 1. The recursive function is going to return the sum of all elements in the "special" array.

We iterate over the "special" array and use a variable to hold the sum of the elements in the current "special" array.

If we get to an integer, we can just add the element to the sum.

If we encounter an array, we call the recursive function on it, passing in the array and its depth, which is the depth of the current array + 1. We add the returned value of the recursive function to the sum.

After we get through all of the elements inside the array, we multiply the sum by the depth of the input array and return the result. 

import java.util.*;

class ProductSum {

  public static int production(List<Object> array, int level){

     int sum = 0;

     for (Object i : array) {

        if( i instanceof ArrayList){

            sum+= production(new ArrayList<>((Collection<?>)i), level+1);

        }else{

            sum+=(int)i;

        }

     }

     return sum * level;

  }

  public static void main(String[] args) {

     

      List<Object> array1 = new ArrayList<>();

      array1.add(5);

      List<Object> array2 = new ArrayList<>();

      array2.add(4);

      array2.add(array1);

      List<Object> array3 = new ArrayList<>();

      array3.add(6);

      array3.add(array2);

      System.out.println(array3);

      System.out.println(production(array3, 1));

     

  }

}