0

I've had this question in a contest, I've tried to answer it using this code (in Java, but you could really use any of the supported languages, contest website linked at the bottom):

static long calcMultisSums(int[] arr)
{
    int sum=0, n=arr.length;
    for(int i=0;i<n;i++)
        sum+=arr[i];

    int mult=0;

   for(int i=0;i<n;i++){
       for(int b=i+1;b<n;b++)
           mult+=arr[b]*arr[i];
   }
   int mult2=0;
    if(n>2){
        mult2=1;
        for(int value : arr) {
            mult2 *= value;
        }      
    }


    return mult+sum+mult2;
}

It works for arrays containing less than 4 elements, but whenever it gets 4 or more elements it ends up giving the wrong answer, which is obviously because it calculates the multiplication of all elements, summation of all elements, and then multiplies each element every one in front of it if the amount of elements in arr > 3. This is obviously a bad solution to the problem, and I'm sure there should be a better implementation for the solution.

Here is the contest in question where you can read the problem and test your answers. (Problem No. 6, Summation Challenge)

Waseem
  • 577
  • 2
  • 4
  • 18
  • Possible duplicate of [Sum of product of all possible subsets of array](https://stackoverflow.com/questions/42993548/sum-of-product-of-all-possible-subsets-of-array) – Michu93 Apr 25 '18 at 20:45

1 Answers1

0

Naive approach:

  1. Make a static variable sum = 0 find all subsets of array (in your example it's called powerset): How to find all the subsets of an array in java?
  2. count product for every set
  3. add it to sum

and better solution is here: Sum of product of all possible subsets of array

Michu93
  • 5,058
  • 7
  • 47
  • 80