Partición del primer número natural N en dos conjuntos de modo que su suma no sea coprima

Dado un número entero N , la tarea es dividir los primeros N números naturales en dos conjuntos no vacíos de modo que la suma de estos conjuntos no sea coprima entre sí. Si es posible, encuentre la partición posible y luego imprima -1 ; de lo contrario, imprima la suma de los elementos de ambos conjuntos.
Ejemplos: 
 

Entrada: N = 5 
Salida: 10 5 
{1, 2, 3, 4} y {5} son las particiones válidas.
Entrada: N = 2 
Salida: -1 
 

Acercarse: 
 

• Si N ≤ 2 , imprima -1 ya que la única partición posible es {1} y {2} donde la suma de ambos conjuntos es coprima entre sí.
• Ahora, si N es impar , entonces ponemos N en un conjunto y los primeros (N – 1) números en otros conjuntos. Entonces la suma de los dos conjuntos será N y N * (N – 1) / 2 y como su mcd es N , no serán coprimos entre sí.
• Si N es par , hacemos lo mismo que antes y la suma de los dos conjuntos será N y N * (N – 1) / 2 . Como N es par, (N – 1) no es divisible por 2, pero N es divisible, lo que da como resultado (N / 2) * (N – 1) y su mcd será N / 2 . Dado que N / 2 es un factor de N , no son coprimos entre sí.

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 find the required sets
void find_set(int n)
{
    // Impossible case
    if (n <= 2) {
        cout << "-1";
        return;
    }
    // Sum of first n-1 natural numbers
    int sum1 = (n * (n - 1)) / 2;
    int sum2 = n;
    cout << sum1 << " " << sum2;
}
 
// Driver code
int main()
{
    int n = 8;
    find_set(n);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// C implementation of the approach
#include <stdio.h>
 
// Function to find the required sets
void find_set(int n)
{
    // Impossible case
    if (n <= 2) {
        printf("-1");
        return;
    }
 
    // Sum of first n-1 natural numbers
    int sum1 = (n * (n - 1)) / 2;
    int sum2 = n;
    printf("%d %d", sum1, sum2);
}
 
// Driver code
int main()
{
    int n = 8;
    find_set(n);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// Java implementation of the approach
import java.io.*;
 
class GFG
{
     
// Function to find the required sets
static void find_set(int n)
{
 
    // Impossible case
    if (n <= 2)
    {
        System.out.println ("-1");
        return;
    }
 
    // Sum of first n-1 natural numbers
    int sum1 = (n * (n - 1)) / 2;
    int sum2 = n;
        System.out.println (sum1 + " " +sum2 );
}
 
// Driver code
public static void main (String[] args)
{
 
    int n = 8;
    find_set(n);
}
}
 
// This code is contributed by jit_t.

# Python implementation of the approach
 
# Function to find the required sets
def find_set(n):
 
    # Impossible case
    if (n <= 2):
        print("-1");
        return;
 
    # Sum of first n-1 natural numbers
    sum1 = (n * (n - 1)) / 2;
    sum2 = n;
    print(sum1, " ", sum2);
 
# Driver code
n = 8;
find_set(n);
 
# This code is contributed by PrinciRaj1992

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to find the required sets
static void find_set(int n)
{
 
    // Impossible case
    if (n <= 2)
    {
        Console.WriteLine("-1");
        return;
    }
 
    // Sum of first n-1 natural numbers
    int sum1 = (n * (n - 1)) / 2;
    int sum2 = n;
        Console.WriteLine(sum1 + " " +sum2 );
}
 
// Driver code
public static void Main ()
{
 
    int n = 8;
    find_set(n);
}
}
 
// This code is contributed by anuj_67...

<script>
 
    // Javascript implementation of the approach
     
    // Function to find the required sets
    function find_set(n)
    {
 
        // Impossible case
        if (n <= 2)
        {
            document.write("-1");
            return;
        }
 
        // Sum of first n-1 natural numbers
        let sum1 = parseInt((n * (n - 1)) / 2, 10);
        let sum2 = n;
          document.write(sum1 + " " +sum2 + "</br>");
    }
     
    let n = 8;
    find_set(n);
 
</script>

28 8

Complejidad de tiempo: O(1)