Dado un número entero N , divida los primeros N números naturales en dos conjuntos de modo que la diferencia absoluta entre su suma sea mínima. La tarea es imprimir la mínima diferencia absoluta que se puede obtener.
Ejemplos :
Entrada: N = 5
Salida: 1
Explicación:
Divide los primeros N (= 5) números naturales en conjuntos {1, 2, 5} (suma = 8) y {3, 4} (suma = 7).
Por lo tanto, la salida requerida es 1.Entrada: N = 6
Salida: 1
Enfoque Ingenuo : Este problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos sumSet1 y sumSet2 para almacenar la suma de los elementos de los dos conjuntos.
- Recorre los primeros N números naturales de N a 1 . Para cada número, verifique si la suma actual de elementos en set1 es menor o igual que la suma de elementos en set2. Si se determina que es cierto, agregue el número recorrido actualmente en set1 y actualice sumSet1 .
- De lo contrario, agregue el valor del número natural actual a set2 y actualice sumSet2 .
- Finalmente, imprima abs(sumSet1 – sumSet2) como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to split the first N
// natural numbers into two sets
// having minimum absolute
// difference of their sums
int minAbsDiff(int N)
{
// Stores the sum of
// elements of set1
int sumSet1 = 0;
// Stores the sum of
// elements of set2
int sumSet2 = 0;
// Traverse first N
// natural numbers
for (int i = N; i > 0; i--) {
// Check if sum of elements of
// set1 is less than or equal
// to sum of elements of set2
if (sumSet1 <= sumSet2) {
sumSet1 += i;
}
else {
sumSet2 += i;
}
}
return abs(sumSet1 - sumSet2);
}
// Driver Code
int main()
{
int N = 6;
cout << minAbsDiff(N);
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function to split the first N
// natural numbers into two sets
// having minimum absolute
// difference of their sums
static int minAbsDiff(int N)
{
// Stores the sum of
// elements of set1
int sumSet1 = 0;
// Stores the sum of
// elements of set2
int sumSet2 = 0;
// Traverse first N
// natural numbers
for(int i = N; i > 0; i--)
{
// Check if sum of elements of
// set1 is less than or equal
// to sum of elements of set2
if (sumSet1 <= sumSet2)
{
sumSet1 += i;
}
else
{
sumSet2 += i;
}
}
return Math.abs(sumSet1 - sumSet2);
}
// Driver code
public static void main (String[] args)
{
int N = 6;
System.out.println(minAbsDiff(N));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach # Function to split the first N # natural numbers into two sets # having minimum absolute # difference of their sums def minAbsDiff(N): # Stores the sum of # elements of set1 sumSet1 = 0 # Stores the sum of # elements of set2 sumSet2 = 0 # Traverse first N # natural numbers for i in reversed(range(N + 1)): # Check if sum of elements of # set1 is less than or equal # to sum of elements of set2 if sumSet1 <= sumSet2: sumSet1 = sumSet1 + i else: sumSet2 = sumSet2 + i return abs(sumSet1 - sumSet2) # Driver Code N = 6 print(minAbsDiff(N)) # This code is contributed by sallagondaavinashreddy7
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to split the first N
// natural numbers into two sets
// having minimum absolute
// difference of their sums
static int minAbsDiff(int N)
{
// Stores the sum of
// elements of set1
int sumSet1 = 0;
// Stores the sum of
// elements of set2
int sumSet2 = 0;
// Traverse first N
// natural numbers
for(int i = N; i > 0; i--)
{
// Check if sum of elements of
// set1 is less than or equal
// to sum of elements of set2
if (sumSet1 <= sumSet2)
{
sumSet1 += i;
}
else
{
sumSet2 += i;
}
}
return Math.Abs(sumSet1 - sumSet2);
}
// Driver code
static void Main()
{
int N = 6;
Console.Write(minAbsDiff(N));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to split the first N
// natural numbers into two sets
// having minimum absolute
// difference of their sums
function minAbsDiff(N)
{
// Stores the sum of
// elements of set1
var sumSet1 = 0;
// Stores the sum of
// elements of set2
var sumSet2 = 0;
// Traverse first N
// natural numbers
for(i = N; i > 0; i--)
{
// Check if sum of elements of
// set1 is less than or equal
// to sum of elements of set2
if (sumSet1 <= sumSet2)
{
sumSet1 += i;
}
else
{
sumSet2 += i;
}
}
return Math.abs(sumSet1 - sumSet2);
}
// Driver code
var N = 6;
document.write(minAbsDiff(N));
// This code is contributed by umadevi9616
</script>
Producción
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente : para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:
Dividir 4 enteros consecutivos en 2 conjuntos da como resultado que la diferencia absoluta mínima de su suma sea igual a 0.
Prueba matemática:
Considerando 4 enteros consecutivos {a 1 , a 2 , a 3 , a 4 }
a 4 = a 3 + 1
a 1 =a 2 – 1
=> a 4 +a 1 = a 3 + 1 + a 2 – 1
=> un 4 + un 1 = un 2 + un 3
Siga los pasos a continuación para resolver el problema:
- Si N % 4 == 0 o N % 4 == 3 , imprima 0 .
- De lo contrario, imprima 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to split the first N
// natural numbers into two sets
// having minimum absolute
// difference of their sums
int minAbsDiff(int N)
{
if (N % 4 == 0 || N % 4 == 3) {
return 0;
}
return 1;
}
// Driver Code
int main()
{
int N = 6;
cout << minAbsDiff(N);
}
Java
// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to split the first N
// natural numbers into two sets
// having minimum absolute
// difference of their sums
static int minAbsDiff(int N)
{
if (N % 4 == 0 || N % 4 == 3)
{
return 0;
}
return 1;
}
// Driver Code
public static void main (String[] args)
{
int N = 6;
System.out.println(minAbsDiff(N));
}
}
// This code is contributed by sallagondaavinashreddy7
Python3
# Python3 program to implement # the above approach # Function to split the first N # natural numbers into two sets # having minimum absolute # difference of their sums def minAbsDiff(N): if (N % 4 == 0 or N % 4 == 3): return 0 return 1 # Driver Code N = 6 print(minAbsDiff(N)) # This code is contributed by sallagondaavinashreddy7
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to split the first N
// natural numbers into two sets
// having minimum absolute
// difference of their sums
static int minAbsDiff(int N)
{
if (N % 4 == 0 ||
N % 4 == 3)
{
return 0;
}
return 1;
}
// Driver Code
public static void Main(String[] args)
{
int N = 6;
Console.WriteLine(minAbsDiff(N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to implement
// the above approach
// Function to split the first N
// natural numbers into two sets
// having minimum absolute
// difference of their sums
function minAbsDiff(N) {
if (N % 4 == 0 || N % 4 == 3) {
return 0;
}
return 1;
}
// Driver Code
var N = 6;
document.write(minAbsDiff(N));
// This code contributed by gauravrajput1
</script>
Producción
1
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA