Tổng sản phẩm của tất cả các tập hợp con có thể có của mảng

Question

Tôi đã viết mã để tìm Tổng sản phẩm của tất cả các tập con có thể có của mảng. Tôi nhận được kết quả mong đợi nhưng tôi không thể làm cho nó đủ nhanh để xóa các trường hợp kiểm tra liên quan đến thời gian.

Có ai có thể giúp tôi tối ưu hóa mã của tôi về tốc độ không?

Đầu vào đầu tiên (testCases) là số lượng testcases. Tùy thuộc vào số lượng testcase, chúng ta sẽ có kích thước của mảng (size) và các phần tử mảng (set).

Ví dụ, một đầu vào hợp lệ sẽ là:

1 
3 
2 3 5 

nơi:

1 là số testcases. 3 là kích thước của bộ kiểm tra và 2 3 5 là các thành phần của bộ đầu vào.

Sản lượng dự kiến ​​là:

71

Việc tính toán cho sản lượng trên là:

{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

Bạn cần sử dụng một chút toán. Giả sử bạn có 3 giá trị, như ví dụ của bạn, nhưng cho phép gọi chúng là A, B và C.

Để có được số tiền của sản phẩm, bạn cần phải tính toán:

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

Bây giờ, nếu chúng tôi tính toán A + B + A*B đầu tiên, gọi đó là Result2, sau đó bạn nhận được:

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

Và chúng tôi lặp lại rằng, do đó

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

Bạn có thể xem mẫu không? Hãy sử dụng với 4 giá trị:

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 

Tóm tắt:

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

Như mã, đây là:

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

Chỉ có một lần lặp, vì vậy O (n).

thử nghiệm

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 

CẬP NHẬT

Mã cũng có thể được thực hiện bằng Java 8 Streams với một biểu thức Lambda, sử dụng IntStream.of(int...) hoặc Arrays.stream(int[]) (chúng cũng giống nhau).

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