Divide los primeros N números naturales en 3 subconjuntos de igual suma

Dado un número entero N , la tarea es verificar si los elementos del rango [1, N] se pueden dividir en tres subconjuntos de suma igual no vacíos. Si es posible , imprima Sí; de lo contrario, imprima No.

Ejemplos: 

Entrada: N = 5 
Salida: Sí 
Los posibles subconjuntos son {1, 4}, {2, 3} y {5}. 
(1 + 4) = (2 + 3) = (5)

Entrada: N = 3 
Salida: No 

Planteamiento: Hay dos casos:  

1. Si N ≤ 3: En este caso, no es posible dividir los elementos en los subconjuntos que satisfacen la condición dada. Por lo tanto, imprima No.
2. Si N > 3: En este caso, solo es posible cuando la suma de todos los elementos del rango [1, N] es divisible por 3 lo que se puede calcular fácilmente como suma = (N * (N + 1)) / 2 . Ahora, si la suma % 3 = 0 , imprima Sí ; de lo contrario , imprima No.

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

// C++ implementation of the approach
#include <iostream>
using namespace std;
 
// Function that returns true
// if the subsets are possible
bool possible(int n)
{
 
    // If n <= 3 then it is not possible
    // to divide the elements in three subsets
    // satisfying the given conditions
    if (n > 3) {
 
        // Sum of all the elements
        // in the range [1, n]
        int sum = (n * (n + 1)) / 2;
 
        // If the sum is divisible by 3
        // then it is possible
        if (sum % 3 == 0) {
            return true;
        }
    }
    return false;
}
 
// Driver code
int main()
{
    int n = 5;
 
    if (possible(n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation of the approach
import java.math.*;
 
class GFG
{
 
    // Function that returns true
    // if the subsets are possible
    public static boolean possible(int n)
    {
     
        // If n <= 3 then it is not possible
        // to divide the elements in three subsets
        // satisfying the given conditions
        if (n > 3)
        {
     
            // Sum of all the elements
            // in the range [1, n]
            int sum = (n * (n + 1)) / 2;
     
            // If the sum is divisible by 3
            // then it is possible
            if (sum % 3 == 0)
            {
                return true;
            }
        }
        return false;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 5;
 
        if (possible(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by Naman_Garg

# Python3 implementation of the approach
 
# Function that returns true
# if the subsets are possible
def possible(n) :
 
    # If n <= 3 then it is not possible
    # to divide the elements in three subsets
    # satisfying the given conditions
    if (n > 3) :
 
        # Sum of all the elements
        # in the range [1, n]
        sum = (n * (n + 1)) // 2;
 
        # If the sum is divisible by 3
        # then it is possible
        if (sum % 3 == 0) :
            return True;
     
    return False;
 
# Driver code
if __name__ == "__main__" :
 
    n = 5;
 
    if (possible(n)) :
        print("Yes");
    else :
        print("No");
         
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function that returns true
// if the subsets are possible
public static bool possible(int n)
{
 
    // If n <= 3 then it is not possible
    // to divide the elements in three subsets
    // satisfying the given conditions
    if (n > 3)
    {
 
        // Sum of all the elements
        // in the range [1, n]
        int sum = (n * (n + 1)) / 2;
 
        // If the sum is divisible by 3
        // then it is possible
        if (sum % 3 == 0)
        {
            return true;
        }
    }
    return false;
}
 
// Driver code
static public void Main ()
{
    int n = 5;
 
    if (possible(n))
        Console.Write("Yes");
    else
        Console.Write("No");
}
}
 
// This code is contributed by ajit

<script>
 
// Javascript implementation of the approach
 
// Function that returns true
// if the subsets are possible
function possible(n)
{
     
    // If n <= 3 then it is not possible
    // to divide the elements in three subsets
    // satisfying the given conditions
    if (n > 3)
    {
         
        // Sum of all the elements
        // in the range [1, n]
        let sum = parseInt((n * (n + 1)) / 2);
 
        // If the sum is divisible by 3
        // then it is possible
        if (sum % 3 == 0)
        {
            return true;
        }
    }
    return false;
}
 
// Driver code
let n = 5;
 
if (possible(n))
    document.write("Yes");
else
    document.write("No");
     
// This code is contributed by rishavmahato348
 
</script>

Yes

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)