Program for sum of n natural numbers

Given a positive integer n, find the sum of the first n natural numbers.

Examples : 

Input: n = 3
Output: 6
Explanation: 1 + 2 + 3 = 6

Input: n = 5
Output: 15
Explanation: 1 + 2 + 3 + 4 + 5 = 15

[Naive Approach] Using Loop - O(n) Time and O(1) Space

 Calculate the sum of all integers from 1 to n by iterating through a loop.

#include <iostream>
using namespace std;
int findSum(int n){
    int sum = 0;
  // iterating over all the numbers 
  // between 1 to n
    for (int i = 1; i <= n; i++)
    {
        sum = sum + i;
    }
    return sum;
}
int main()
{
    int n = 5;
    cout << findSum(n);
    return 0;
}

#include <stdio.h>
int findSum(int n){
    int sum = 0;
  // iterating over all the numbers 
  // between 1 to n
    for (int i = 1; i <= n; i++)
    {
        sum = sum + i;
    }
    return sum;
}
int main()
{
    int n = 5;
    printf("%d", findSum(n));
    return 0;
}

import java.io.*;

class GfG{
    static int findSum(int n){
        int sum = 0;
      // iterating over all the numbers 
      // between 1 to n
        for (int i= 1; i <= n; i++) 
        {
            sum = sum + i;
        }
        return sum;
    }
    public static void main(String args[])
    {
        int n = 5;
        System.out.println(findSum(n));
    } 
}

def findSum(n):
    sum = 0
    i = 1
    # Iterating over all the numbers between 1 to n
    while i <= n:
        sum = sum + i
        i = i + 1
    return sum
if __name__ == "__main__":
    n = 5
    print(findSum(n))

using System;
class GfG{
    static int findSum(int n)
    {
        int sum = 0;
      // iterating over all the numbers 
      // between 1 to n
        for (int i = 1; i <= n; i++) 
        {
            sum = sum + i;
        }
        return sum;
    }
    public static void Main()
    {
        int n = 5;
        Console.Write(findSum(n));
    } 
}

function findSum(n)
{
   let sum = 0;
  // iterating over all the numbers 
  // between 1 to n
   for (let i = 1; i <= n; i++) 
   {
     sum = sum + i;
    }
    return sum;
}
// Driver Code
let n = 5;
console.log(findSum(n));

15

[Alternative Approach] Using Recursion -O(n) and O(n) Space

In this approach, we use recursion to find the sum of the first n natural numbers. The function calls itself with (n-1) until it reaches the base case of n = 1. Each call adds the current value of n to the sum of smaller values, effectively building the result in a top-down manner.

#include <iostream>
using namespace std;
int findSum (int  n){
    // base condition
    if (n == 1 )
     return  1 ;
    return n + findSum(n - 1); 
}
int main() {
    int n = 5 ;
    cout <<  findSum(n); 
    return 0;
}

public class Gfg {
    static int findSum(int n) {
        // base condition
        if (n == 1)
            return 1;
        return n + findSum(n - 1);
    }
    public static void main(String[] args) {
        int n = 5;
        System.out.println(findSum(n));
    }
}

def findSum(n):
    # base condition
    if n == 1:
        return 1
    return n + findSum(n - 1)

if __name__ == "__main__":
    n = 5
    print(findSum(n))

using System;
class Gfg
{
    static int findSum(int n)
    {
        // base condition
        if (n == 1)
            return 1;
        return n + findSum(n - 1);
    }

    static void Main()
    {
        int n = 5;
        Console.WriteLine(findSum(n));
    }
}

function findSum(n) {
    // base condition
    if (n == 1)
        return 1;
    return n + findSum(n - 1);
}
//Driver code 
let n = 5;
console.log(findSum(n));

[Expected Approach] Formula Based Method- O(1) Time and O(1) Space

Sum of first n natural numbers = (n * (n+1)) / 2

For example: n = 5
Sum = (5 * (5 + 1)) / 2 = (5 * 6) / 2 = 30 / 2 = 15

How does this work?

We can prove this formula using induction.
It is true for n = 1 and n = 2
For n = 1, sum = 1 * (1 + 1)/2 = 1
For n = 4, sum = 4* (4 + 1)/2 = 10
Let it be true for k = n-1.
Sum of k numbers = (k * (k+1))/2
Putting k = n-1, we get
Sum of k numbers = ((n-1) * (n-1+1))/2
= (n - 1) * n / 2
If we add n, we get,
Sum of n numbers = n + (n - 1) * n / 2
= (2n + n² - n)/2
= n * (n + 1)/2

#include<iostream>
using namespace std;
int findSum(int n)
{
    // Using mathematical formula to compute
    // sum of first n natural numbers
    return n * (n + 1) / 2;
}
int main()
{
   int n = 5;
   cout << findSum(n);
   return 0;
} 

#include<stdio.h>
int findSum(int n)
{
    // Using mathematical formula to compute
    // sum of first n natural numbers
    return n * (n + 1) / 2;
}
int main()
{
    int n = 5;
    printf("%d", findSum(n));
    return 0;
} 

import java.io.*;
class GfG{
    static int findSum(int n)
    {
        // Using mathematical formula to compute
        // sum of first n natural numbers
        return n * (n + 1) / 2;
    }
    public static void main(String args[])
    {
        int n = 5;
        System.out.println(findSum(n));
    }
}

def findSum(n):
    # Using mathematical formula to compute
    # sum of first n natural numbers
    return n * (n + 1) // 2
if __name__ == "__main__":
    n = 5
    print(findSum(n))

using System;
class GFG
    static int findSum(int n)
    {
        // Using mathematical formula to compute
        // sum of first n natural numbers
        return n * (n + 1) / 2;
    }
    
    public static void Main()
    {
        int n = 5;
        Console.Write(findSum(n));
    }
}

function findSum(n)
{
    // Using mathematical formula to compute
    // sum of first n natural numbers
    return n * (n + 1) / 2;
}
// Driver Code
var n = 5;
console.log(findSum(n));

15