There is given a sum and you have to find whether this sum is resultant of summation of first n natural numbers or not. If it is summation of first n natural numbers then simply print value of n if that is not the case then simply print -1.
Examples :
Input : 15 Output : 5 Explanation : sum = 1 + 2 + 3 + 4 + 5 sum = 15 Input : 11 Output : -1 Explanation : There is no natural number n for which sum of all natural number 1 to n is 11.
Naive Approach :
Run a loop from 1 and store the summation of i if this sum is equal to given sum then break the loop and print the value of i if sum is greater than given sum then return -1.
Implementation in C++:
// CPP Program to find value // of n for which sum of 1 to n // is given sum #include <bits/stdc++.h> using namespace std; // Function that returns value of n int find_n(long long int sum) { long long int result = 0; // If sum is not positive // Then return -1; if (sum <= 0) return -1; // Run a loop for (int i = 1;; i++) { result += i; // If given number has been // Found then return number if (result == sum) return i; // If sum not Found // return -1 if (result > sum) return -1; } } // Driver Code int main(void) { int a = 11; int b = 15; cout << find_n(a) << endl; cout << find_n(b) << endl; return 0; }
Output
-1 5
The complexity of above problem is about to O(n).
Efficient Approach :
The above problem can be solved easily by using binary search method we know by the formula that the sum of first n natural number is – n * ( n + 1 ) / 2.
We initialize beg = 0 and end = 1000000 and we will find mid if sum of all numbers from 1 to mid is equal to given sum then return mid else if it greater than given sum then decrease high by mid-1 else increase beg by mid+1.
Run above loop while beg is less than or equal to end.
Implementation in C++:
// CPP Program to find value // of n for which the sum of 1 to n // is a given sum #include <iostream> using namespace std; // Function that returns the value of n int find_n(long long int sum) { long long int beg = 0, mid, end = 10000000000, rs; // Run the loop while beg is less than or equal to n while (beg <= end) { // Find the value of mid mid = (beg + end + 1) >> 1; // Find the sum of all natural numbers from // 1 to mid rs = mid * (mid + 1) / 2; // If the result is found, then return it if (rs == sum) return mid; // If the result lies on the right-hand side else if (rs < sum) beg = mid + 1; // If the result lies on the left-hand side else end = mid - 1; } // If the sum is not found return -1; } // Driver Code int main(void) { int a = 11; int b = 15; cout << find_n(a) << endl; cout << find_n(b) << endl; return 0; }
Output
-1 5
Time Complexity of above code is about to log(n).