Divide los cuadrados de los primeros N números naturales en dos conjuntos con una mínima diferencia absoluta de sus sumas

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 + 9

Tomemos 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 = 4

Por 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) = 4

Restando 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>
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *