The sum of the product of all possible subsets of the array

Question

I wrote code to search for the sum of the product of all possible subsets of an array. I get the expected result, but I can't do it fast enough to clear the time tests.

Can someone help me in optimizing my code for speed?

The first entry (testCases) is the number of test places. Depending on the number of test files, we will have the size of the array (size) and array elements (set).

For example, valid input:

1 3 2 3 5 

Where:

1 - the number of test places. 3 - the size of the test set, and 2 3 5 - elements of the input data set.

Expected Result:

71

Calculation for the above result:

  {2}, {3}, {5}, {2, 3}, {3, 5}, {2, 5}, {2, 3, 5} => 2 3 5 6 15 10 30 => 2 + 3 + 5 + 6 + 15 + 10 + 30 => 71 

---

 import java.util.Scanner; public class Test { static int printSubsets(int set[]) { int n = set.length; int b = 0; for (int i = 0; i < (1 << n); i++) { int a = 1; for (int j = 0; j < n; j++){ if ((i & (1 << j)) > 0) { a *= set[j]; }} b += a; } return b; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int testCases = scanner.nextInt(); for (int i = 0; i < testCases; i++) { int size = scanner.nextInt(); int set[] = new int[size]; for (int j = 0; j < set.length; j++) { set[j] = scanner.nextInt(); } int c = printSubsets(set); System.out.println((c - 1)); } scanner.close(); } } 

Answer 1

You need to use a little math. Suppose you have 3 values, for example your example, but call them A , B and C

To get the sum of products, you need to calculate:

 Result3 = A + B + C + A*B + A*C + B*C + A*B*C = A + B + A*B + (1 + A + B + A*B) * C 

Now, if we first calculate A + B + A*B , calling it Result2 , you will get:

 Result2 = A + B + A*B Result3 = Result2 + (1 + Result2) * C 

And we repeat that

 Result2 = A + (1 + A) * B Result1 = A Result2 = Result1 + (1 + Result1) * B 

Do you see the template? Let use this with 4 values:

 Result4 = A + B + C + D + A*B + A*C + A*D + B*C + B*D + C*D + A*B*C + A*B*D + A*C*D + B*C*D + A*B*C*D = A + B + C + A*B + A*C + B*C + A*B*C + (1 + A + B + C + A*B + A*C + B*C + A*B*C) * D = Result3 + (1 + Result3) * D 

Summary:

 Result1 = A Result2 = Result1 + (1 + Result1) * B Result3 = Result2 + (1 + Result2) * C Result4 = Result3 + (1 + Result3) * D 

As a code, this is:

 private static long sumProduct(int... input) { long result = 0; for (int value : input) result += (result + 1) * value; return result; } 

Only one iteration, therefore O (n).

Test

 System.out.println(sumProduct(2, 3)); System.out.println(sumProduct(2, 3, 5)); System.out.println(sumProduct(2, 3, 5, 7)); 

Exit

 11 71 575 

UPDATE

The code can also be executed using Java 8 Streams with a Lambda expression using IntStream.of(int...) or Arrays.stream(int[]) (they do the same).

 // Using IntStream with result as int private static int sumProduct(int... input) { return IntStream.of(input).reduce((a, b) -> a + (1 + a) * b).getAsInt(); } 

 // Using Arrays with result as long private static long sumProduct(int... input) { return Arrays.stream(input) .asLongStream() .reduce((a, b) -> a + (1 + a) * b) .getAsLong(); }