Comprobar si un número dado se puede expresar como par-suma de la suma de los primeros X números naturales

Dado un número entero N , la tarea es verificar si N es la suma de un par de números enteros que se pueden expresar como la suma de los primeros X números naturales, donde X puede ser cualquier número entero positivo. Si cumple la condición requerida. Escriba “SÍ”. De lo contrario, escriba “NO”.

Ejemplos:

Entrada: N = 25
Salida: SÍ
Explicación:
=> 10 + 15 = 25
Dado que 10 y 15 son la suma de los primeros 4 y 5 números naturales respectivamente, la respuesta es SÍ.

Entrada: N = 512
Salida: NO

Enfoque: La idea es elegir una suma de números naturales M que sea menor que igual a N y verificar si M y N – M son las sumas de la secuencia de los primeros números naturales. Siga los pasos a continuación para resolver el problema:

• Iterar sobre un ciclo para calcular la suma de K números naturales:

 Suma de K números naturales = K * (K + 1) / 2 

• Luego, calcule la suma restante y verifique si la suma es la suma mediante la siguiente ecuación:

 Y = N – Suma de K Número natural 
=> Y = N – (K * (K + 1) / 2) 

• Verifica si el número calculado arriba satisface la condición requerida calculando la raíz cuadrada del doble del número y verifica si el producto de números consecutivos es igual al doble del número.

 M * (M + 1) == 2 * Y, donde M = √ (2 * Y) 

• Si se cumple la condición anterior, escriba «SÍ». De lo contrario, escriba “NO”.

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

// C++ program of the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to check if the number
// is pair-sum of sum of first X
// natural numbers
void checkSumOfNatural(int n)
{
    int i = 1;
    bool flag = false;
     
    // Check if the given number
    // is sum of pair of special numbers
    while (i * (i + 1) < n * 2)
    {
         
        // X is the sum of first
        // i natural numbers
        int X = i * (i + 1);
         
        // t = 2 * Y
        int t = n * 2 - X;
        int k = sqrt(t);
         
        // Condition to check if
        // Y is a special number
        if (k * (k + 1) == t)
        {
            flag = true;
            break;
        }
        i += 1;
    }
     
    if (flag)
        cout << "YES";
    else
        cout << "NO";
}
 
// Driver Code
int main()
{
    int n = 25;
     
    // Function call
    checkSumOfNatural(n);
 
    return 0;
}
 
// This code is contributed by rutvik_56

// Java program of the above approach
import java.util.*;
import java.lang.*;
 
class GFG{
 
// Function to check if the number
// is pair-sum of sum of first X
// natural numbers
static void checkSumOfNatural(int n)
{
    int i = 1;
    boolean flag = false;
     
    // Check if the given number
    // is sum of pair of special numbers
    while (i * (i + 1) < n * 2)
    {
         
        // X is the sum of first
        // i natural numbers
        int X = i * (i + 1);
         
        // t = 2 * Y
        int t = n * 2 - X;
        int k = (int)Math.sqrt(t);
         
        // Condition to check if
        // Y is a special number
        if(k * (k + 1) == t)
        {
            flag = true;
            break;
        }
        i += 1;
    }
     
    if (flag)
        System.out.println("YES");
    else
        System.out.println("NO");
}
 
// Driver Code
public static void main (String[] args)
{
    int n = 25;
     
    // Function call
    checkSumOfNatural(n);
}
}
 
// This code is contributed by offbeat

# Python3 program of the
# above approach
 
import math
 
# Function to check if the number
# is pair-sum of sum of first X
# natural numbers
def checkSumOfNatural(n):
    i = 1
    flag = False
     
    # Check if the given number
    # is sum of pair of special numbers
    while i*(i + 1) < n * 2:
         
        # X is the sum of first
        # i natural numbers
        X = i*(i + 1)
         
        # t = 2 * Y
        t = n * 2 - X
        k = int(math.sqrt(t))
         
        # Condition to check if
        # Y is a special number
        if k*(k + 1) == t:
            flag = True
            break
        i += 1
     
    if flag:
        print('YES')
    else:
        print('NO')
 
# Driver Code       
if __name__ == "__main__":
    n = 25
     
    # Function Call
    checkSumOfNatural(n)

// C# program of
// the above approach
using System;
class GFG{
 
// Function to check if the number
// is pair-sum of sum of first X
// natural numbers
static void checkSumOfNatural(int n)
{
  int i = 1;
  bool flag = false;
 
  // Check if the given number
  // is sum of pair of special numbers
  while (i * (i + 1) < n * 2)
  {
    // X is the sum of first
    // i natural numbers
    int X = i * (i + 1);
 
    // t = 2 * Y
    int t = n * 2 - X;
    int k = (int)Math.Sqrt(t);
 
    // Condition to check if
    // Y is a special number
    if(k * (k + 1) == t)
    {
      flag = true;
      break;
    }
    i += 1;
  }
 
  if (flag)
    Console.WriteLine("YES");
  else
    Console.WriteLine("NO");
}
 
// Driver Code
public static void Main(String[] args)
{
  int n = 25;
 
  // Function call
  checkSumOfNatural(n);
}
}
 
// This code is contributed by Rajput-Ji

<script>
// javascript program of the above approach// Function to check if the number
// is pair-sum of sum of first X
// natural numbers
function checkSumOfNatural(n)
{
    var i = 1;
    var flag = false;
     
    // Check if the given number
    // is sum of pair of special numbers
    while (i * (i + 1) < n * 2)
    {
         
        // X is the sum of first
        // i natural numbers
        var X = i * (i + 1);
         
        // t = 2 * Y
        var t = n * 2 - X;
        var k = parseInt(Math.sqrt(t));
         
        // Condition to check if
        // Y is a special number
        if(k * (k + 1) == t)
        {
            flag = true;
            break;
        }
        i += 1;
    }
     
    if (flag)
        document.write("YES");
    else
        document.write("NO");
}
 
// Driver Code
var n = 25;
     
// Function call
checkSumOfNatural(n);
 
// This code is contributed by Princi Singh
</script>

YES

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)