He escrito un código para encontrar la suma del producto de todos los subconjuntos posibles de la matriz. Obtengo el resultado esperado, pero no puedo hacerlo lo suficientemente rápido como para borrar los casos de prueba relacionados con el tiempo.
¿Alguien puede ayudarme a optimizar mi código para la velocidad?
La primera entrada (testCases) es el número de casos de prueba. Dependiendo de la cantidad de casos de prueba, tendremos el tamaño de la matriz (tamaño) y los elementos de la matriz (conjunto).
Por ejemplo, una entrada válida sería:
1 3 2 3 5dónde:
1es el número de casos de prueba.3es el tamaño del conjunto de prueba y2 3 5son los elementos del conjunto de entrada.
La salida esperada es:
71
El cálculo para la salida anterior es:
{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(); } }Necesitas usar un poco de matemática. Digamos que tiene 3 valores, como su ejemplo, pero llamémoslos A , B y C .
Para obtener la suma de los productos, debe calcular:
Result3 = A + B + C + A*B + A*C + B*C + A*B*C = A + B + A*B + (1 + A + B + A*B) * C Ahora, si primero calculamos A + B + A*B , llamándolo Result2 , entonces obtienes:
Result2 = A + B + A*B Result3 = Result2 + (1 + Result2) * CY lo repetimos, así que
Result2 = A + (1 + A) * B Result1 = A Result2 = Result1 + (1 + Result1) * B¿Puedes ver el patrón? Usemos eso con 4 valores:
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) * DResumen:
Result1 = A Result2 = Result1 + (1 + Result1) * B Result3 = Result2 + (1 + Result2) * C Result4 = Result3 + (1 + Result3) * DComo código, esto es:
private static long sumProduct(int... input) { long result = 0; for (int value : input) result += (result + 1) * value; return result; }Solo una iteración, entonces O(n) .
Prueba
System.out.println(sumProduct(2, 3)); System.out.println(sumProduct(2, 3, 5)); System.out.println(sumProduct(2, 3, 5, 7));Producción
11 71 575ACTUALIZAR
El código también se puede hacer usando Java 8 Streams con una expresión Lambda, usando IntStream.of(int...) o Arrays.stream(int[]) (hacen lo mismo).
// 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(); }