Find if given number is sum of first n natural numbers
Given a number s (1 <= s <= 1000000000). If this number is the sum of first n natural number then print n, otherwise print -1.
Examples:
Input: s = 10
Output: n = 4
Explanation: 1 + 2 + 3 + 4 = 10Input: s = 17
Output: n = -1
Explanation: 17 can’t be expressed as a sum of first n natural numbers as sum of first 5 natural numbers is 15 and sum of first 6 natural numbers is 21
Finding if given number is sum of first n natural numbers using Brute Force:
The idea is to keep adding numbers starting from 1 and if the sum of the numbers become equal to s, then return the count of numbers added so far. If the sum becomes greater than s, then return -1 as it is impossible to express s as sum of first n natural numbers.
Step by step approach:
- Maintain a variable sum = 0 to calculate the running sum of numbers.
- Iterate a loop from i = 1 to s
- Add i to sum
- If sum == s, return i
- Else if sum > s, return -1
Below is the implementation of the above approach:
C++
// C++ program for above implementation #include <iostream> using namespace std; // Function to find no. of elements // to be added from 1 to get sum = s int findS( int s) { int sum = 0; // Start adding numbers from 1 for ( int i = 1; sum < s; i++) { sum += i; // If sum becomes equal to s // return i if (sum == s) return i; } return -1; } // Drivers code int main() { int s = 15; cout << findS(s); return 0; } |
Java
// Java program for above implementation class GFG { // Function to find no. of elements // to be added from 1 to get sum = s static int findS( int s) { int sum = 0 ; // Start adding numbers from 1 for ( int i = 1 ; sum < s; i++) { sum += i; // If sum becomes equal to s // return i if (sum == s) return i; } return - 1 ; } // Drivers code public static void main(String[] args) { int s = 15 ; System.out.println(findS(s)); } } // This code is contributed by Azkia Anam. |
Python3
# Python3 program to check if # given number is sum of first n # natural numbers # Function to find no. of elements # to be added from 1 to get sum = s def findS(s): _sum = 0 i = 1 # Start adding numbers from 1 while (_sum < s): _sum + = i # If sum becomes equal to s # return i if _sum = = s: return i i + = 1 return - 1 # Driver code s = 15 print (findS(s)) # This code is contributed by "Abhishek Sharma 44". |
C#
// C# program for above implementation using System; class GFG { // Function to find no. of elements // to be added from 1 to get sum = s static int findS( int s) { int sum = 0; // Start adding numbers from 1 for ( int i = 1; sum < s; i++) { sum += i; // If sum becomes equal to s // return i if (sum == s) return i; } return -1; } // Drivers code public static void Main() { int s = 15; Console.WriteLine(findS(s)); } } // This code is contributed by vt_m. |
Javascript
<script> // Javascript program for above implementation // Function to find no. of elements // to be added from 1 to get sum = s function findS(s) { var sum = 0; // Start adding numbers from 1 for (i = 1; sum < s; i++) { sum += i; // If sum becomes equal to s // return i if (sum == s) return i; } return -1; } // Drivers code var s = 15; document.write(findS(s)); // This code is contributed by Rajput-Ji </script> |
PHP
<?php // PHP program for above implementation // Function to find no. of elements // to be added from 1 to get sum = s function findS( $s ) { $sum = 0; // Start adding numbers from 1 for ( $i = 1; $sum < $s ; $i ++) { $sum += $i ; // If sum becomes equal // to s return i if ( $sum == $s ) return $i ; } return -1; } // Drivers code $s = 15; echo findS( $s ); // This code is contributed by Sam007 ?> |
5
Time Complexity: O(√s), where s is the number we need to check as the sum of first n natural numbers
Auxiliary Space: O(1)
Finding if given number is sum of first n natural numbers using Mathematical formula:
The idea is to use the formula of the sum of first N natural numbers to compute the value of the N. Below is the illustration:
⇾ 1 + 2 + 3 + …. N = S
⇾ (N * (N + 1)) / 2 = S
⇾ N * (N + 1) = 2 * S
⇾ N2 + N – 2 * S = 0Therefore, Calculate the solution of the quadratic equation using Sridharacharya Formula and check if the solution is an integer or not. If Yes then the solution exists. Otherwise, the given number is not sum of first N natural number.
Step by step algorithm:
- Calculate the positive root of equation: N2 + N – 2 * S = 0
- Check if the root is an integer or not
- Return root if it is an integer, else return -1.
Below is the implementation of the above approach:
C++
// C++ program of the above // approach #include <bits/stdc++.h> #define ll long long using namespace std; // Function to check if the // s is the sum of first N // natural number ll int isvalid(ll int s) { // Solution of Quadratic Equation float k = (-1 + sqrt (1 + 8 * s)) / 2; // Condition to check if the // solution is a integer if ( ceil (k) == floor (k)) return k; else return -1; } // Driver Code int main() { int s = 15; // Function Call cout << isvalid(s); return 0; } |
Java
// Java program of the above // approach import java.util.*; class GFG { // Function to check if the // s is the sum of first N // natural number public static int isvalid( int s) { // Solution of Quadratic Equation double k = (- 1.0 + Math.sqrt( 1 + 8 * s)) / 2 ; // Condition to check if the // solution is a integer if (Math.ceil(k) == Math.floor(k)) return ( int )k; else return - 1 ; } // Driver code public static void main(String[] args) { int s = 15 ; // Function call System.out.print(isvalid(s)); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program of the above # approach import math # Function to check if the # s is the sum of first N # natural number def isvalid(s): # Solution of Quadratic Equation k = ( - 1 + math.sqrt( 1 + 8 * s)) / 2 # Condition to check if the # solution is a integer if (math.ceil(k) = = math.floor(k)): return int (k) else : return - 1 # Driver Code s = 15 # Function Call print (isvalid(s)) # This code is contributed by vishu2908 |
C#
// C# program of the above // approach using System; class GFG { // Function to check if the // s is the sum of first N // natural number public static int isvalid( int s) { // Solution of Quadratic Equation double k = (-1.0 + Math.Sqrt(1 + 8 * s)) / 2; // Condition to check if the // solution is a integer if (Math.Ceiling(k) == Math.Floor(k)) return ( int )k; else return -1; } // Driver code public static void Main( string [] args) { int s = 15; // Function call Console.Write(isvalid(s)); } } // This code is contributed by Chitranayal |
Javascript
<script> // Javascript program of the above // approach // Function to check if the // s is the sum of first N // natural number function isvalid(s) { // Solution of Quadratic Equation let k = (-1.0 + Math.sqrt(1 + 8 * s)) / 2; // Condition to check if the // solution is a integer if (Math.ceil(k) == Math.floor(k)) return k; else return -1; } // Driver code let s = 15; // Function call document.write(isvalid(s)); </script> |
5
Time Complexity: O(log(s)) because it is using sqrt() function
Auxiliary Space: O(1)