Given an integer N, the task is to check if N is the sum of a pair of integers which can be expressed as the sum of first X natural numbers, where X can be any positive integer. If satisfies the required condition. Print “YES”. Otherwise, print “NO”.
Examples:
Input: N = 25
Output: YES
Explanation:
=> 10 + 15 = 25
Since 10 and 15 are the sum of first 4 and 5 natural numbers respectively, the answer is YES.Input: N = 512
Output: NO
Approach: The idea is to choose a sum of natural numbers M which is less than equal to N and check if M and N – M are the sums of the sequence of the first few natural numbers. Follow the steps below to solve the problem:
- Iterate over a loop to calculate the sum of K natural numbers:
Sum of K natural numbers = K * (K + 1) / 2
- Then, calculate the remaining sum and check if the sum is the sum by the following equation:
Y = N – Sum of K Natural number
=> Y = N – (K * (K + 1) / 2)
- Check if the number calculated above satisfies the required condition by calculating the square root of the twice of the number and check if the product of consecutive numbers is equal to the twice of the number.
M * (M + 1) == 2 * Y, where M = √ (2 * Y)
- If the above condition is satisfied, print “YES”. Otherwise, print “NO”.
Below is the implementation of the above approach:
C++
// 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 Codeint main(){ int n = 25; // Function call checkSumOfNatural(n); return 0;}// This code is contributed by rutvik_56 |
Java
// Java program of the above approachimport 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 Codepublic static void main (String[] args){ int n = 25; // Function call checkSumOfNatural(n);}}// This code is contributed by offbeat |
Python3
# Python3 program of the # above approachimport math# Function to check if the number# is pair-sum of sum of first X # natural numbersdef 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#
// C# program of // the above approachusing 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 Codepublic static void Main(String[] args){ int n = 25; // Function call checkSumOfNatural(n);}}// This code is contributed by Rajput-Ji |
Javascript
<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 Codevar n = 25; // Function call checkSumOfNatural(n);// This code is contributed by Princi Singh </script> |
Output
YES
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach 2 :
This code checks whether a given number n can be expressed as the sum of two special numbers, where a special number is defined as the sum of the first X natural numbers for some positive integer X.
The approach used in the code is as follows:
- Given a number n, calculate the largest value of X such that X*(X+1)/2 <= n. This is done using the quadratic formula for finding roots of the equation X*(X+1)/2 = n. We take the floor of the result because X must be an integer.
- For each value of i from 1 to X, calculate j = n – (i*(i+1))/2. This is the other number that n must be paired with to form the sum of two special numbers.
- Check whether j is greater than i and less than or equal to X. This ensures that i and j are distinct positive integers that are both less than or equal to X.
- If there exists such a pair of i and j, set the flag to true and break out of the loop.
- If flag is true, output “YES“, indicating that n can be expressed as the sum of two special numbers. Otherwise, output “NO”.
The time complexity of this algorithm is O(sqrt(n)), since the loop from 1 to X runs for at most sqrt(n) iterations.
C++
#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){ // Calculate the largest X such that X*(X+1)/2 <= n int X = floor((-1 + sqrt(1 + 8 * n))/2); // Check if the given number // is sum of pair of special numbers bool flag = false; for (int i = 1; i <= X; i++) { int j = n - (i*(i+1))/2; if (j > i && j <= X) { flag = true; break; } } if (flag) cout << "YES"; else cout << "NO";}// Driver Codeint main(){ int n = 25; // Function call checkSumOfNatural(n); return 0;} |
Java
import java.util.*;public class GFG { // Function to check if the number is pair-sum of // sum of first X natural numbers public static void checkSumOfNatural(int n) { // Calculate the largest X such that X*(X+1)/2 <= n int X = (int) Math.floor((-1 + Math.sqrt(1 + 8 * n)) / 2); // Check if the given number is sum of pair of special numbers boolean flag = false; for (int i = 1; i <= X; i++) { int j = n - (i * (i + 1)) / 2; if (j > i && j <= X) { flag = true; break; } } if (flag) System.out.println("YES"); else System.out.println("NO"); } public static void main(String[] args) { int n = 25; // Function call checkSumOfNatural(n); // This code is contributed by Shivam Tiwari }} |
Python3
import math# Function to check if the number# is a pair-sum of the sum of the first X# natural numbersdef checkSumOfNatural(n): # Calculate the largest X such that X*(X+1)/2 <= n X = int((-1 + math.sqrt(1 + 8 * n)) / 2) # Check if the given number is a sum of a pair of special numbers flag = False for i in range(1, X+1): j = n - (i * (i+1)) // 2 if j > i and j <= X: flag = True break if flag: print("YES") else: print("NO")# Driver Codeif __name__ == "__main__": n = 25 # Function call checkSumOfNatural(n) |
C#
using System;class GFG{ // Function to check if the number // is a pair-sum of the sum of the first X // natural numbers static void CheckSumOfNatural(int n) { // Calculate the largest X such that X*(X+1)/2 <= n int X = (int)((-1 + Math.Sqrt(1 + 8 * n)) / 2); // Check if the given number is a sum of a pair of special numbers bool flag = false; for (int i = 1; i <= X; i++) { int j = n - (i * (i + 1)) / 2; if (j > i && j <= X) { flag = true; break; } } if (flag) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } } // Driver Code static void Main(string[] args) { int n = 25; // Function call CheckSumOfNatural(n); // This code is Contributed By Shubham Tiwari. }} |
Javascript
function checkSumOfNatural(n) { // Calculate the largest X such that X*(X+1)/2 <= n let X = Math.floor((-1 + Math.sqrt(1 + 8 * n)) / 2); // Check if the given number is a sum of a pair of special numbers let flag = false; for (let i = 1; i <= X; i++) { let j = n - (i * (i + 1)) / 2; if (j > i && j <= X) { flag = true; break; } } if (flag) { console.log("YES"); } else { console.log("NO"); }}// Driver Codelet n = 25;// Function callcheckSumOfNatural(n);// This code is contributed by Shivam Tiwari. |
Output
NO
Time Complexity : O(N)
Auxiliary Space : O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
