Partición de suma más cercana (en dos subconjuntos) de números del 1 al n

Dada una secuencia entera 1, 2, 3, 4, …, n . La tarea es dividirlo en dos conjuntos A y B de tal manera que cada elemento pertenezca exactamente a un conjunto y |sum(A) – sum(B)| es el mínimo posible. Imprime el valor de |sum(A) – sum(B)| .
Ejemplos: 
 

Entrada: 3 
Salida: 0 
A = {1, 2} y B = {3} ans |sum(A) – sum(B)| = |3 – 3| = 0.
Entrada: 6 
Salida: 0 
A = {1, 3, 4} y B = {2, 5} ans |sum(A) – sum(B)| = |3 – 3| = 0.
Entrada: 5 
Salida: 1 
 

Enfoque: Tome mod = n % 4 , 
 

1. Si mod = 0 o mod = 3 , imprima 0 .
2. Si mod = 1 o mod = 2 , imprima 1 .

Esto se debe a que los grupos se elegirán como A = {N, N – 3, N – 4, N – 7, N – 8, …..}, B = {N – 1, N – 2, N – 5, N – 6, …..} 
Comenzando de N a 1, coloque el primer elemento en el grupo A y luego alterne cada 2 elementos en B, A, B, A, ….. 
 

• Cuando n % 4 = 0: N = 8, A = {1, 4, 5, 8} y B = {2, 3, 6, 7}
• Cuando n % 4 = 1: N = 9, A = {1, 4, 5, 8, 9} y B = {2, 3, 6, 7}
• Cuando n % 4 = 2: N = 10, A = {1, 4, 5, 8, 9} y B = {2, 3, 6, 7, 10}
• Cuando n % 4 = 3: N = 11, A = {1, 4, 5, 8, 9} y B = {2, 3, 6, 7, 10, 11}

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum required
// absolute difference
int minAbsDiff(int n)
{
    int mod = n % 4;
 
    if (mod == 0 || mod == 3)
        return 0;
 
    return 1;
}
 
// Driver code
int main()
{
    int n = 5;
    cout << minAbsDiff(n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
// Function to return the minimum required
// absolute difference
 
    static int minAbsDiff(int n)
    {
        int mod = n % 4;
        if (mod == 0 || mod == 3)
        {
            return 0;
        }
        return 1;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 5;
        System.out.println(minAbsDiff(n));
    }
}
 
// This code is contributed by Rajput-JI

# Python3 implementation of the approach
 
# Function to return the minimum required
# absolute difference
def minAbsDiff(n) :
    mod = n % 4;
 
    if (mod == 0 or mod == 3) :
        return 0;
 
    return 1;
 
# Driver code
if __name__ == "__main__" :
 
    n = 5;
    print(minAbsDiff(n))
     
# This code is contributed by Ryuga

// C# implementation of the
// above approach
using System;
 
class GFG
{
         
    // Function to return the minimum 
    // required absolute difference
    static int minAbsDiff(int n)
    {
        int mod = n % 4;
        if (mod == 0 || mod == 3)
        {
            return 0;
        }
        return 1;
    }
 
    // Driver code
    static public void Main ()
    {
        int n = 5;
        Console.WriteLine(minAbsDiff(n));
    }
}
 
// This code is contributed by akt_mit

<?php
// PHP implementation of the approach
 
// Function to return the minimum
// required absolute difference
function minAbsDiff($n)
{
    $mod = $n % 4;
 
    if ($mod == 0 || $mod == 3)
        return 0;
 
    return 1;
}
 
// Driver code
$n = 5;
echo minAbsDiff($n);
 
// This code is contributed by Tushil.
?>

<script>
    // Javascript implementation of the above approach
     
    // Function to return the minimum 
    // required absolute difference
    function minAbsDiff(n)
    {
        let mod = n % 4;
        if (mod == 0 || mod == 3)
        {
            return 0;
        }
        return 1;
    }
     
    let n = 5;
      document.write(minAbsDiff(n));
 
</script>

1

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)