Dado un número entero N , la tarea es dividir los cuadrados de los primeros N ( siempre un múltiplo de 8 ) números naturales en dos conjuntos de modo que la diferencia de las sumas de sus subconjuntos se minimice. Imprima ambos subconjuntos como la respuesta requerida.
Ejemplos:
Entrada: N = 8
Salida:
0
1 16 36 49
4 9 25 64
Explicación: Los cuadrados de los primeros N números naturales son {1, 4, 9, 16, 25, 36, 49, 64}
Subconjuntos {1, 16, 36, 49} y {4, 9, 25, 64} tienen suma 102. Por lo tanto, la diferencia de sus sumas es 0.Entrada: N = 16
Salida:
0
1 16 36 49 81 144 196 225
4 9 25 64 100 121 169 256
Enfoque ingenuo: la idea es generar todos los pares posibles de subconjuntos dividiendo cuadrados de los primeros N números naturales entre ellos y calcular subconjuntos cuya diferencia de los subconjuntos suma. Imprime el par de subconjuntos para los que se encuentra que la diferencia de su suma es mínima.
Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar las propiedades matemáticas de la suma de números cuadrados continuos . Observe que siempre es posible dividir 8 números cuadrados contiguos en 2 conjuntos de modo que su diferencia de suma de subconjuntos sea 0 .
Prueba:
8 números cuadrados contiguos se pueden dividir en 2 subconjuntos cuya diferencia en la suma es 0.
4 números cuadrados contiguos se pueden representar como k 2 , (k + 1) 2 , (k + 2) 2 y (k + 3) 2 .Tomemos el primer y cuarto elemento en el subconjunto A. Por lo tanto,
Suma de A = k 2 + (k+3) 2
= 2k 2 + 6k + 9Tomemos el segundo y tercer elemento en el subconjunto B. Por lo tanto,
Suma de B = (k + 1) 2 + (k + 2) 2
= 2k 2 + 6k + 5
Diferencia de subconjunto = Suma de A – Suma de B = 4Por lo tanto, 4 números cuadrados contiguos se pueden dividir en 2 subconjuntos que tienen la diferencia de su suma como 4.
Ahora, digamos, la array de cuadrados contiguos es arr[] = {a1, a2, a3, a4, a5, a6, a7, a8}.
De la propiedad anterior se puede escribir que:
a1 + a4 – (a2 + a3) = 4 y
a5 + a8 – (a6 + a7) = 4Restando las ecuaciones anteriores:
a1 + a4 – (a2 + a3) – (a5 + a8 – (a6 + a7)) = 0
Por lo tanto, (a1 + a4 + a6 + a7) – (a2 + a3 + a5 + a8) = 0
Por lo tanto, 8 números cuadrados contiguos se pueden dividir en 2 subconjuntos que tienen una diferencia de 0.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable para almacenar la diferencia mínima del subconjunto y declárela en 0 .
- Inicialice la variable cnt para almacenar el número de bloques de tamaño 8 y divida N entre 8 y guárdelo en la variable cnt .
- Inicialice una partición de string y almacene el patrón de partición de N elementos concatenando la string «ABBABAAB» , cnt número de veces donde «ABBABAAB» representa el subconjunto en el que debe ir cada elemento en un subarreglo de tamaño 8 .
- Inicialice 2 vectores A y B para almacenar elementos del subconjunto A y el subconjunto B.
- Itere un ciclo sobre el rango [0, N – 1] e inserte (i + 1) 2 en el vector A si el patrón [i] es ‘A’ . De lo contrario, inserte (i + 1) 2 en el vector B .
- Después de los pasos anteriores, imprima la diferencia mínima del subconjunto, el vector A y el vector B.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to partition squares of N // natural number in two subset void minimumSubsetDifference(int N) { // Store the count of blocks of size 8 int blockOfSize8 = N / 8; // Partition of block of 8 element string str = "ABBABAAB"; // Store the minimum subset difference int subsetDifference = 0; // Partition of N elements to minimize // their subset sum difference string partition = ""; while (blockOfSize8--) { partition += str; } // Store elements of subset A and B vector<int> A, B; for (int i = 0; i < N; i++) { // If element is of type A if (partition[i] == 'A') { A.push_back((i + 1) * (i + 1)); } // If the element is of type B else { B.push_back((i + 1) * (i + 1)); } } // Print the minimum subset difference cout << subsetDifference << "\n"; // Print the first subset for (int i = 0; i < A.size(); i++) cout << A[i] << " "; cout << "\n"; // Print the second subset for (int i = 0; i < B.size(); i++) cout << B[i] << " "; } // Driver Code int main() { int N = 8; // Function Call minimumSubsetDifference(N); return 0; }
Java
// Java program for the above approach import java.util.Arrays; class GFG{ // Function to partition squares of N // natural number in two subset static void minimumSubsetDifference(int N) { // Store the count of blocks of size 8 int blockOfSize8 = N / 8; // Partition of block of 8 element String str = "ABBABAAB"; // Store the minimum subset difference int subsetDifference = 0; // Partition of N elements to minimize // their subset sum difference String partition = ""; while (blockOfSize8-- > 0) { partition += str; } // Store elements of subset A and B int A[] = new int[N]; int B[] = new int[N]; int x = 0, y = 0; for(int i = 0; i < N; i++) { // If element is of type A if (partition.charAt(i) == 'A') { A[x++] = ((i + 1) * (i + 1)); } // If the element is of type B else { B[y++] = ((i + 1) * (i + 1)); } } // Print the minimum subset difference System.out.println(subsetDifference); // Print the first subset for(int i = 0; i < x; i++) System.out.print(A[i] + " "); System.out.println(); // Print the second subset for(int i = 0; i < y; i++) System.out.print(B[i] + " "); } // Driver Code public static void main(String[] args) { int N = 8; // Function Call minimumSubsetDifference(N); } } // This code is contributed by shailjapriya
Python3
# Python3 program for the above approach # Function to partition squares of N # natural number in two subset def minimumSubsetDifference(N): # Store the count of blocks of size 8 blockOfSize8 = N // 8 # Partition of block of 8 element str = "ABBABAAB" # Store the minimum subset difference subsetDifference = 0 # Partition of N elements to minimize # their subset sum difference partition = "" while blockOfSize8 != 0: partition = partition + str blockOfSize8 = blockOfSize8 - 1 # Store elements of subset A and B A = [] B = [] for i in range(N): # If element is of type A if partition[i] == 'A': A.append((i + 1) * (i + 1)) # If the element is of type B else: B.append((i + 1) * (i + 1)) # Print the minimum subset difference print(subsetDifference) # Print the first subset for i in A: print(i, end = " ") print() # Print the second subset for i in B: print(i, end = " ") # Driver Code N = 8 # Function call minimumSubsetDifference(N) # This code is contributed by shailjapriya
C#
// C# program for the above approach using System; class GFG{ // Function to partition squares of N // natural number in two subset static void minimumSubsetDifference(int N) { // Store the count of blocks of size 8 int blockOfSize8 = N / 8; // Partition of block of 8 element string str = "ABBABAAB"; // Store the minimum subset difference int subsetDifference = 0; // Partition of N elements to minimize // their subset sum difference string partition = ""; while (blockOfSize8-- > 0) { partition += str; } // Store elements of subset A and B int []A = new int[N]; int []B = new int[N]; int x = 0, y = 0; for(int i = 0; i < N; i++) { // If element is of type A if (partition[i] == 'A') { A[x++] = ((i + 1) * (i + 1)); } // If the element is of type B else { B[y++] = ((i + 1) * (i + 1)); } } // Print the minimum subset difference Console.WriteLine(subsetDifference); // Print the first subset for(int i = 0; i < x; i++) Console.Write(A[i] + " "); Console.WriteLine(); // Print the second subset for(int i = 0; i < y; i++) Console.Write(B[i] + " "); } // Driver Code public static void Main(string[] args) { int N = 8; // Function Call minimumSubsetDifference(N); } } // This code is contributed by AnkitRai01
Javascript
<script> // javascript program to implement // the above approach // Function to partition squares of N // natural number in two subset function minimumSubsetDifference(N) { // Store the count of blocks of size 8 let blockOfSize8 = N / 8; // Partition of block of 8 element let str = "ABBABAAB"; // Store the minimum subset difference let subsetDifference = 0; // Partition of N elements to minimize // their subset sum difference let partition = ""; while (blockOfSize8-- > 0) { partition += str; } // Store elements of subset A and B let A = []; let B = []; let x = 0, y = 0; for(let i = 0; i < N; i++) { // If element is of type A if (partition[i] == 'A') { A[x++] = ((i + 1) * (i + 1)); } // If the element is of type B else { B[y++] = ((i + 1) * (i + 1)); } } // Print the minimum subset difference document.write(subsetDifference + "<br/>"); // Print the first subset for(let i = 0; i < x; i++) document.write(A[i] + " "); document.write("<br/>"); // Print the second subset for(let i = 0; i < y; i++) document.write(B[i] + " "); } // Driver code let N = 8; // Function Call minimumSubsetDifference(N); // This code is contributed by splevel62. </script>
0 1 16 36 49 4 9 25 64
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por math_lover y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA