Sum of product of all possible subsets of array

Question

I have written a code to find Sum of product of all possible subsets of array. I'm getting the expected output but I'm not able to make it fast enough to clear time related test cases.

Can anyone help me in optimizing my code for speed?

First input (testCases) is the number of testcases. Depending on number of testcase, we will have size of array (size) and array elements (set).

For example, a valid input would be:

1
3
2 3 5

where:

1 is the number of testcases. 3 is the size of the test set and 2 3 5 are the elements of the input set.

The expected output is:

71

The calculation for the above output is:

    {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();
    }
}

Pedology

Could you clarify your problem? If I understand you correctly, your algorithm should calculate (2 * 3) + (2 * 5) + (2 * 3 * 5) + (3 * 5) = 61. – Woodcut

The individual elements are also valid subsets. You need to add 2 + 3 + 5 to 61. So you get 71. – Emlyn

You are looking to optimize your code I assume? " fast enough to clear time related test cases." – Purine

Joginder, Can you add what time complexity you are trying to achieve? – Emlyn

@anacron, In question, I have been given Time Limit: 10.0 sec(s) for each input. I am able to achieve 20.0 sec(s) only. – Pedology

Answer 1

You need to use a little math. Lets say you have 3 values, like your example, but lets call them A, B, and C.

To get 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 calculate A + B + A*B first, calling it Result2, then you get:

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

And we repeat that, so

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

Can you see the pattern? Let's use that 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 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, so O(n).

Test

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

Output

11
71
575

UPDATE

Code can also be done using Java 8 Streams with a Lambda expression, using either 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();
}

Weltanschauung