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