The problem statement here is to calculate the sum of n natural numbers, for example, if n=4, then we should calculate the value of sum, where sum = 1+2+3+4 = 10. There are more than one ways to solve the problem, we will see different approaches to the same problem and this is a very trivial problem so, we will directly get into the solution without much discussion.

Let us see frame the problem statement in an easy-to-understand way. Here, the input will be-

```
// input
n = 6
```

and the desired output will be-

```
// output
sum = 1+2+3+4+5+6 = 21
```

Now, let us see the solution of the program using various approaches and we will also discuss the time and space complexity of the proposed solutions.

## Using Recursive Approach

This is the easiest way to understand the solution. Recursion means calling itself again and again. Here, we will simply call the function, again and again, to add all the natural numbers until the given input. So, the simplest formula we can derive is:

`Sum of n natural numbers = n + sum of (n-1) natural numbers`

The above approach can be converted into a program as shown below. The sum of the first 50 natural numbers is considered in the program below.

```
public class sum {
static int naturalSum(int n) {
if (n > 0) {
return n + naturalSum(n - 1);
}
return 0;
}
public static void main(String[] args) {
int n = 50;
System.out.println(naturalSum(n));
}
}
```

```
#include <stdio.h>
// using recursion
int naturalSum(int n)
{
if (n > 0)
{
return n + naturalSum(n - 1);
}
return 0;
}
void main()
{
int n = 50;
printf("The sum of %d natural nos. is: %d.", n, naturalSum(n));
}
```

Here, the time complexity of the solution using the recursive approach is O(n) and the space complexity is O(n). Similarly, the problem can be solved using the iterative approach as well.

## Using Iterative Approach

The benefit of using loops here is the efficiency of space complexity in loops. In the recursive approach, every time a recursive call is made a new activation record for the function is made in the memory stack, this is an unnecessary use of memory though this is a trivial problem we should always try to be efficient.

```
public class sum {
public static void main(String[] args) {
int n = 50, sum = 0;
// using loop
while (n > 0) {
sum += n--;
}
System.out.println(sum);
}
}
```

```
#include <stdio.h>
void main()
{
int n = 50, sum = 0;
int d = n;
while (n > 0)
{
sum += n--;
}
printf("The sum of %d natural nos. is: %d.", d, sum);
}
```

The time complexity of the solution using the loop is the same as that of the recursive approach i.e. O(n) but, the space complexity is reduced and for this solution, it is O(1) or constant.

## Using the Mathematical Formula

We all have studied the mathematical formula for the sum of n natural numbers in our schools. The formula for the sum of first n natural numbers is:

`Sum = [n*(n+1)]/2`

Using this formula, we can reduce the time complexity to constant. Let us see the code for it.

```
public class sum {
public static void main(String[] args) {
int n = 50, sum = 0;
// using formula
sum = n*(n+1)/2;
System.out.println(sum);
}
}
```

```
#include <stdio.h>
void main()
{
int n = 50, sum = 0;
sum = n * (n + 1) / 2;
printf("The sum of %d natural nos. is: %d.", n, sum);
}
```

The time complexity for the solution using the formula is reduced to O(1) and also the space complexity is O(1). **Hence, it is the optimal solution for this problem. **But, you should remember the merits and demerits of all the approaches for clarity in decision-making and requirements.

## 0 Comments