Dado un número n, divida los primeros n números naturales (1, 2, … n) en dos subconjuntos de manera que la diferencia entre las sumas de dos subconjuntos sea mínima.
Ejemplos:
Input : n = 4
Output : First subset sum = 5,
Second subset sum = 5.
Difference = 0
Explanation:
Subset 1: 1 4
Subset 2: 2 3
Input : n = 6
Output: First subset sum = 10,
Second subset sum = 11.
Difference = 1
Explanation :
Subset 1: 1 3 6
Subset 2: 2 4 5
Enfoque:
El enfoque se basa en el hecho de que cuatro números consecutivos se pueden dividir en dos grupos colocando los dos elementos centrales en un grupo y los elementos de las esquinas en otro grupo. Entonces, si n es un múltiplo de 4, entonces su diferencia será 0, por lo tanto, la suma de un conjunto será la mitad de la suma de N elementos que se pueden calcular usando sum = n*(n+1)/2 .
Hay Otros tres casos a considerar en los que no podemos dividir en grupos de 4, lo que dejará un resto de 1, 2 y 3:
a) Si deja un resto de 1, entonces todos los demás elementos n-1 se agrupan en un grupo de 4 por tanto, su suma será int(suma/2) y la otra mitad de la suma será int(suma/2+1) y su diferencia siempre será 1.
b)Los pasos mencionados anteriormente se seguirán en el caso de n%4 == 2 también. Aquí formamos grupos de tamaño 4 para elementos de 3 en adelante. Los elementos restantes serían 1 y 2. 1 va en un grupo y 2 va en otro grupo.
c) Cuando n%4 == 3, entonces agrupe n-3 elementos en grupos de 4. Los elementos que quedan fuera serán 1, 2 y 3, en los que 1 y 2 irán a un conjunto y 3 al otro conjunto que eventualmente hace que la diferencia sea 0 y la suma de cada conjunto sea sum/2.
A continuación se muestra la implementación del enfoque anterior:
CPP
// CPP program to Minimize the absolute
// difference of sum of two subsets
#include <bits/stdc++.h>
using namespace std;
// function to print difference
void subsetDifference(int n)
{
// summation of n elements
int s = n * (n + 1) / 2;
// if divisible by 4
if (n % 4 == 0) {
cout << "First subset sum = "
<< s / 2;
cout << "\nSecond subset sum = "
<< s / 2;
cout << "\nDifference = " << 0;
}
else {
// if remainder 1 or 2. In case of remainder
// 2, we divide elements from 3 to n in groups
// of size 4 and put 1 in one group and 2 in
// group. This also makes difference 1.
if (n % 4 == 1 || n % 4 == 2) {
cout << "First subset sum = "
<< s / 2;
cout << "\nSecond subset sum = "
<< s / 2 + 1;
cout << "\nDifference = " << 1;
}
// We put elements from 4 to n in groups of
// size 4. Remaining elements 1, 2 and 3 can
// be divided as (1, 2) and (3).
else
{
cout << "First subset sum = "
<< s / 2;
cout << "\nSecond subset sum = "
<< s / 2;
cout << "\nDifference = " << 0;
}
}
}
// driver program to test the above function
int main()
{
int n = 6;
subsetDifference(n);
return 0;
}
Java
// Java program for Minimize the absolute
// difference of sum of two subsets
import java.util.*;
class GFG {
// function to print difference
static void subsetDifference(int n)
{
// summation of n elements
int s = n * (n + 1) / 2;
// if divisible by 4
if (n % 4 == 0) {
System.out.println("First subset sum = " + s / 2);
System.out.println("Second subset sum = " + s / 2);
System.out.println("Difference = " + 0);
}
else {
// if remainder 1 or 2. In case of remainder
// 2, we divide elements from 3 to n in groups
// of size 4 and put 1 in one group and 2 in
// group. This also makes difference 1.
if (n % 4 == 1 || n % 4 == 2) {
System.out.println("First subset sum = " + s / 2);
System.out.println("Second subset sum = " + ((s / 2) + 1));
System.out.println("Difference = " + 1);
}
// We put elements from 4 to n in groups of
// size 4. Remaining elements 1, 2 and 3 can
// be divided as (1, 2) and (3).
else
{
System.out.println("First subset sum = " + s / 2);
System.out.println("Second subset sum = " + s / 2);
System.out.println("Difference = " + 0);
}
}
}
/* Driver program to test above function */
public static void main(String[] args)
{
int n = 6;
subsetDifference(n);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 code to Minimize the absolute
# difference of sum of two subsets
# function to print difference
def subsetDifference( n ):
# summation of n elements
s = int(n * (n + 1) / 2)
# if divisible by 4
if n % 4 == 0:
print("First subset sum = ", int(s / 2))
print("Second subset sum = ",int(s / 2))
print("Difference = " , 0)
else:
# if remainder 1 or 2. In case of remainder
# 2, we divide elements from 3 to n in groups
# of size 4 and put 1 in one group and 2 in
# group. This also makes difference 1.
if n % 4 == 1 or n % 4 == 2:
print("First subset sum = ",int(s/2))
print("Second subset sum = ",int(s/2)+1)
print("Difference = ", 1)
# We put elements from 4 to n in groups of
# size 4. Remaining elements 1, 2 and 3 can
# be divided as (1, 2) and (3).
else:
print("First subset sum = ", int(s / 2))
print("Second subset sum = ",int(s / 2))
print("Difference = " , 0)
# driver code to test the above function
n = 6
subsetDifference(n)
# This code is contributed by "Sharad_Bhardwaj".
C#
// C# program for Minimize the absolute
// difference of sum of two subsets
using System;
class GFG {
// function to print difference
static void subsetDifference(int n)
{
// summation of n elements
int s = n * (n + 1) / 2;
// if divisible by 4
if (n % 4 == 0) {
Console.WriteLine("First "
+ "subset sum = " + s / 2);
Console.WriteLine("Second "
+ "subset sum = " + s / 2);
Console.WriteLine("Difference"
+ " = " + 0);
}
else {
// if remainder 1 or 2. In case
// of remainder 2, we divide
// elements from 3 to n in groups
// of size 4 and put 1 in one
// group and 2 in group. This
// also makes difference 1.
if (n % 4 == 1 || n % 4 == 2) {
Console.WriteLine("First "
+ "subset sum = " + s / 2);
Console.WriteLine("Second "
+ "subset sum = " + ((s / 2)
+ 1));
Console.WriteLine("Difference"
+ " = " + 1);
}
// We put elements from 4 to n
// in groups of size 4. Remaining
// elements 1, 2 and 3 can
// be divided as (1, 2) and (3).
else
{
Console.WriteLine("First "
+ "subset sum = " + s / 2);
Console.WriteLine("Second "
+ "subset sum = " + s / 2);
Console.WriteLine("Difference"
+ " = " + 0);
}
}
}
/* Driver program to test above
function */
public static void Main()
{
int n = 6;
subsetDifference(n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to Minimize the absolute
// difference of sum of two subsets
// function to print difference
function subsetDifference($n)
{
// summation of n elements
$s = $n * ($n + 1) / 2;
// if divisible by 4
if ($n % 4 == 0)
{
echo "First subset sum = "
,floor($s / 2);
echo "\nSecond subset sum = "
,floor($s / 2);
echo "\nDifference = " , 0;
}
else
{
// if remainder 1 or 2.
// In case of remainder
// 2, we divide elements
// from 3 to n in groups
// of size 4 and put 1 in
// one group and 2 in
// group. This also makes
// difference 1.
if ($n % 4 == 1 || $n % 4 == 2)
{
echo"First subset sum = "
, floor($s / 2);
echo "\nSecond subset sum = "
, floor($s / 2 + 1);
echo"\nDifference = " ,1;
}
// We put elements from 4
// to n in groups of
// size 4. Remaining
// elements 1, 2 and 3 can
// be divided as (1, 2)
// and (3).
else
{
echo "First subset sum = "
,floor($s / 2);
echo "\nSecond subset sum = "
, floor($s / 2);
echo"\nDifference = " , 0;
}
}
}
// Driver code
$n = 6;
subsetDifference($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to Minimize the absolute
// difference of sum of two subsets
// function to print difference
function subsetDifference(n)
{
// summation of n elements
let s = n * (n + 1) / 2;
// if divisible by 4
if (n % 4 == 0)
{
document.write("First subset sum = " + Math.floor(s / 2));
document.write("<br> Second subset sum = " + Math.floor(s / 2));
document.write("<br> Difference = " + 0);
}
else
{
// if remainder 1 or 2.
// In case of remainder
// 2, we divide elements
// from 3 to n in groups
// of size 4 and put 1 in
// one group and 2 in
// group. This also makes
// difference 1.
if (n % 4 == 1 || n % 4 == 2)
{
document.write("First subset sum = " + Math.floor(s / 2));
document.write("<br> Second subset sum = " + Math.floor(s / 2 + 1));
document.write("<br> Difference = " + 1);
}
// We put elements from 4
// to n in groups of
// size 4. Remaining
// elements 1, 2 and 3 can
// be divided as (1, 2)
// and (3).
else
{
document.write( "First subset sum = " + Math.floor(s / 2));
document.write( "<br> Second subset sum = " + Math.floor(s / 2));
document.write("<br> Difference = " + 0);
}
}
}
// Driver code
let n = 6;
subsetDifference(n);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción
First subset sum = 10 Second subset sum = 11 Difference = 1
Complejidad de Tiempo : O(1)
Espacio Auxiliar : O(1)