QUESTION 31 · Loop Applications

How is the sum of the first n natural numbers accumulated in a loop?

2 marks

Answer

Start sum at zero and add each integer from 1 through n.

After adding i, sum contains 1 + 2 + ... + i.
For n = 0, no additions are required and the result is 0.

Write a C program to find the sum of the first n natural numbers using a loop.

5 marks

Answer in brief

The sum of the first n natural numbers is 1 + 2 + ... + n. A loop can build this sum one value at a time.

Algorithm

Read n and check the supported range.
Set sum to 0.
For i from 1 through n, add i to sum.
Print sum.

Worked trace

For n = 4, sum begins at 0. Adding 1 gives 1, adding 2 gives 3, adding 3 gives 6 and adding 4 gives 10. The next counter value is 5, so the loop ends and the program prints 10.

Why initialise to zero?

Zero is the starting value for addition: adding it does not change the result. Using an uninitialised automatic variable would not provide a valid starting sum. For n = 0, the loop is skipped and the already initialised result remains zero.

Equivalent while loop

int i = 1;
while (i <= n) {
    sum += i;
    ++i;
}

Time and space complexity

The for version performs n additions and n counter updates. Each uses constant work in the fixed-width model, so total time grows in proportion to n: O(n). Only n, i and sum are stored, so auxiliary space is O(1). The formula n * (n + 1) / 2 is a different constant-operation method, but the multiplication must fit its type.

Input limits

The sample accepts 0 through 10000 and uses long long for the total. These limits keep the supported calculations within the standard minimum range of that type. The user must supply an integer representable by int.

C program and output

Download .c Open compiler

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
int main(void)
{
    int n;
    long long sum = 0;
    if (scanf("%d", &n) != 1 || n < 0 || n > 10000) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 1; i <= n; ++i) { sum += i; }
    printf("Sum = %lld\n", sum);
    return 0;
}

Sample input and output

Input

Output

Sum = 10