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