Dado un número par N , la tarea es dividir todas las N potencias de 2 en dos conjuntos de modo que la diferencia de su suma sea mínima.
Ejemplos:
Entrada: n = 4
Salida: 6
Explicación:
Aquí n = 4 lo que significa que tenemos 2 1 , 2 2 , 2 3 , 2 4 . La forma más óptima de dividirlo en dos grupos con elementos iguales es 2 4 + 2 1 en un grupo y 2 2 + 2 3 en otro grupo dando una diferencia mínima posible de 6.
Entrada: n = 8
Salida: 30
Explicación:
Aquí n = 8 lo que significa que tenemos 2 1 , 2 2 , 2 3 , 2 4 , 2 5 , 2 6 , 27 , 2 8 . La forma más óptima de dividirlo en dos grupos con el mismo elemento es 2 8 + 2 1 + 2 2 + 2 3 en un grupo y 2 4 + 2 5 + 2 6 + 2 7 en otro grupo dando una diferencia mínima posible de 30 .
Enfoque: Para resolver el problema mencionado anteriormente, debemos seguir los pasos que se detallan a continuación:
- En el primer grupo agrega el elemento más grande que es 2 N .
- Después de agregar el primer número en un grupo, agregue N/2 – 1 elementos más a este grupo, donde los elementos deben comenzar desde la menor potencia de dos o desde el comienzo de la secuencia.
Por ejemplo : si N = 4, agregue 2 4 al primer grupo y agregue N/2 – 1 , es decir, 1 elemento más a este grupo, que es el menor, lo que significa que es 2 1 . - El elemento restante de la secuencia forma los elementos del segundo grupo.
- Calcule la suma para ambos grupos y luego encuentre la diferencia absoluta entre los grupos que eventualmente será el mínimo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the minimum
// difference possible by splitting
// all powers of 2 up to N into two
// sets of equal size
#include<bits/stdc++.h>
using namespace std;
void MinDiff(int n)
{
// Store the largest
int val = pow(2, n);
// Form two separate groups
int sep = n / 2;
// Initialize the sum
// for two groups as 0
int grp1 = 0;
int grp2 = 0;
// Insert 2 ^ n in the
// first group
grp1 = grp1 + val;
// Calculate the sum of
// least n / 2 -1 elements
// added to the first set
for(int i = 1; i < sep; i++)
grp1 = grp1 + pow(2, i);
// Sum of remaining
// n / 2 - 1 elements
for(int i = sep; i < n; i++)
grp2 = grp2 + pow(2, i);
// Min Difference between
// the two groups
cout << (abs(grp1 - grp2));
}
// Driver code
int main()
{
int n = 4;
MinDiff(n);
}
// This code is contributed by Bhupendra_Singh
Java
// Java program to find the minimum
// difference possible by splitting
// all powers of 2 up to N into two
// sets of equal size
import java.lang.Math;
class GFG{
public static void MinDiff(int n)
{
// Store the largest
int val = (int)Math.pow(2, n);
// Form two separate groups
int sep = n / 2;
// Initialize the sum
// for two groups as 0
int grp1 = 0;
int grp2 = 0;
// Insert 2 ^ n in the
// first group
grp1 = grp1 + val;
// Calculate the sum of
// least n / 2 -1 elements
// added to the first set
for(int i = 1; i < sep; i++)
grp1 = grp1 + (int)Math.pow(2, i);
// Sum of remaining
// n / 2 - 1 elements
for(int i = sep; i < n; i++)
grp2 = grp2 + (int)Math.pow(2, i);
// Min difference between
// the two groups
System.out.println(Math.abs(grp1 - grp2));
}
// Driver Code
public static void main(String args[])
{
int n = 4;
MinDiff(n);
}
}
// This code is contributed by grand_master
Python3
# Python3 program to find the minimum # difference possible by splitting # all powers of 2 up to N into two # sets of equal size def MinDiff(n): # Store the largest val = 2 ** n # Form two separate groups sep = n // 2 # Initialize the sum # for two groups as 0 grp1 = 0 grp2 = 0 # Insert 2 ^ n in the # first group grp1 = grp1 + val # Calculate the sum of # least n / 2 -1 elements # added to the first set for i in range(1, sep): grp1 = grp1 + 2 ** i # sum of remaining # n / 2 - 1 elements for i in range(sep, n): grp2 = grp2 + 2 ** i # Min Difference between # the two groups print(abs(grp1 - grp2)) # Driver code if __name__=='__main__': n = 4 MinDiff(n)
C#
// C# program to find the minimum
// difference possible by splitting
// all powers of 2 up to N into two
// sets of equal size
using System;
class GFG{
public static void MinDiff(int n)
{
// Store the largest
int val = (int)Math.Pow(2, n);
// Form two separate groups
int sep = n / 2;
// Initialize the sum
// for two groups as 0
int grp1 = 0;
int grp2 = 0;
// Insert 2 ^ n in the
// first group
grp1 = grp1 + val;
// Calculate the sum of
// least n / 2 -1 elements
// added to the first set
for(int i = 1; i < sep; i++)
grp1 = grp1 + (int)Math.Pow(2, i);
// Sum of remaining
// n / 2 - 1 elements
for(int i = sep; i < n; i++)
grp2 = grp2 + (int)Math.Pow(2, i);
// Min difference between
// the two groups
Console.Write(Math.Abs(grp1 - grp2));
}
// Driver Code
public static void Main()
{
int n = 4;
MinDiff(n);
}
}
// This code is contributed by Akanksha_Rai
Javascript
<script>
// javascript program to find the minimum
// difference possible by splitting
// all powers of 2 up to N into two
// sets of equal size
function MinDiff(n)
{
// Store the largest
var val = parseInt( Math.pow(2, n));
// Form two separate groups
var sep = n / 2;
// Initialize the sum
// for two groups as 0
var grp1 = 0;
var grp2 = 0;
// Insert 2 ^ n in the
// first group
grp1 = grp1 + val;
// Calculate the sum of
// least n / 2 -1 elements
// added to the first set
for (i = 1; i < sep; i++)
grp1 = grp1 + parseInt( Math.pow(2, i));
// Sum of remaining
// n / 2 - 1 elements
for (i = sep; i < n; i++)
grp2 = grp2 + parseInt( Math.pow(2, i));
// Min difference between
// the two groups
document.write(Math.abs(grp1 - grp2));
}
// Driver Code
var n = 4;
MinDiff(n);
// This code is contributed by gauravrajput1
</script>
Producción:
6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)