In this blog post, we learn how to write a C Program to find a given number is the sum of first n natural numbers?. We will write the C Program to find the given number is the sum of first n natural numbers or not using the loop and binary search. Let see an example,
Input : data = 10 Output : n => 4 1 + 2 + 3 + 4 = 10 Input : data = 17 Output : n => -1 17 can't be expressed as a the sum of consecutive from 1.
What are Natural numbers?
Natural numbers are the positive integers or non-negative integers which starts from 1 and ends at infinity, such as:
1,2,3,4,5,6,7,8,9,10,……,∞
Algorithm to find the given number is the sum of first n natural numbers
1. Ask the user to enter an integer number. Suppose n = 10, where n is an integer variable.
int n = 10;
2. Start adding numbers from i = 1 to n (10).
3. Check if the sum is equal to n, return i. It means your entered number is the sum of natural numbers.
4. If the sum of n natural number is not equal to n, return -1, and print an error message.
C Program to find given number is the sum of first n natural numbers
#include <stdio.h> int findSum(int data) { int sum = 0, i, isEqual = 0; // Start adding numbers from 1 for (i = 1; sum < data; i++) { sum += i; // If sum becomes equal to data // return i if (sum == data) { isEqual = i; } } return isEqual; } int main() { int data = 15, isSumOfNaturalNumber = 0; printf("Enter number = "); scanf("%d", &data); isSumOfNaturalNumber = findSum(data); if(isSumOfNaturalNumber) { printf ("Sum of Natural number 1 to %d\n",isSumOfNaturalNumber); } else { printf("It is not a sum of 1 to n Natural number\n"); } return 0; }
Output:
Enter number = 10
Sum of Natural number 1 to 4
C Program to find given number is the sum of first n natural numbers using Binary Search:
Algorithm:
1- Initialize l = 1 and r = data / 2. 2- Apply a binary search from l to r. a) Find mid = (l+r) / 2 b) Find sum from 1 to mid using formula mid*(mid+1)/2 c) If sum of mid natural numbers is equal to data, return mid. d) Else if sum > data, r = mid - 1. e) Else sum < data, l = mid + 1. 3- Return 0, if not possible.
#include <stdio.h> int findSum(int data) { int l = 1, r = (data / 2) + 1; int isEqual = 0; // Apply Binary search while (l <= r) { // Find mid int mid = (l + r) / 2; // find sum of 1 to mid natural numbers // using formula int sum = mid * (mid + 1) / 2; // If sum is equal to n // return mid if (sum == data) { isEqual= mid; break; } // If greater than n // do r = mid-1 else if (sum > data) { r = mid - 1; } // else do l = mid + 1 else { l = mid + 1; } } return isEqual; } int main() { int data = 15, isSumOfNaturalNumber = 0; printf("Enter number = "); scanf("%d", &data); isSumOfNaturalNumber = findSum(data); if(isSumOfNaturalNumber) { printf ("Sum of Natural number 1 to %d\n",isSumOfNaturalNumber); } else { printf("It is not a sum of 1 to n Natural number\n"); } return 0; }
Output:
Enter number = 10
Sum of Natural number 1 to 4