Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Sum of First N Natural Numbers

EASYProblemSolveExternal Links

Description

Given a positive integer n, calculate the sum of all natural numbers from 1 to n (inclusive).

The natural numbers are the counting numbers starting from 1: {1, 2, 3, 4, ...}. The sum of the first n natural numbers means adding up all integers from 1 through n.

For example, if n = 4, the sum is 1 + 2 + 3 + 4 = 10.

This is one of the most fundamental problems in mathematics and programming. It teaches the difference between a brute force iterative approach and a mathematical formula that gives the answer instantly — a pattern that appears throughout algorithm design.

Examples

Example 1

Input: n = 3

Output: 6

Explanation: The natural numbers from 1 to 3 are {1, 2, 3}. Adding them up: 1 + 2 + 3 = 6.

Example 2

Input: n = 5

Output: 15

Explanation: The natural numbers from 1 to 5 are {1, 2, 3, 4, 5}. Adding them up: 1 + 2 + 3 + 4 + 5 = 15.

Example 3

Input: n = 1

Output: 1

Explanation: There is only one natural number from 1 to 1, which is 1 itself. The sum is simply 1. This is the smallest valid input and serves as a boundary case.

Example 4

Input: n = 10

Output: 55

Explanation: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55. A useful sanity check: the sum of the first 10 natural numbers is 55.

Constraints

  • 1 ≤ n ≤ 10^4

Editorial

Brute Force

Intuition

The most natural way to compute the sum of numbers from 1 to n is exactly how you would do it by hand: start at 1, add each successive number to a running total, and stop when you reach n.

Imagine you are stacking coins. You place 1 coin, then add 2 more on top, then 3 more, then 4 more, and so on until you have added n coins in the last batch. The total number of coins in the stack is the sum we want.

We initialize a variable sum to 0, then loop through every integer from 1 to n, adding each one to sum. After the loop finishes, sum holds the answer.

Step-by-Step Explanation

Let's trace through with n = 5:

Step 1: Initialize sum = 0. We have not added any numbers yet.

Step 2: i = 1. Add 1 to sum: sum = 0 + 1 = 1.

Step 3: i = 2. Add 2 to sum: sum = 1 + 2 = 3.

Step 4: i = 3. Add 3 to sum: sum = 3 + 3 = 6.

Step 5: i = 4. Add 4 to sum: sum = 6 + 4 = 10.

Step 6: i = 5. Add 5 to sum: sum = 10 + 5 = 15.

Step 7: Loop ends (i has exceeded n). Return sum = 15.

Iterative Summation — Adding Numbers 1 to N — Watch how we accumulate a running sum by adding each natural number from 1 to n one at a time.

Algorithm

  1. Initialize sum = 0
  2. For each integer i from 1 to n:
    • Add i to sum
  3. Return sum

Code

#include <iostream>
using namespace std;

class Solution {
public:
    int sumOfNaturalNumbers(int n) {
        int sum = 0;
        
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        
        return sum;
    }
};
class Solution:
    def sumOfNaturalNumbers(self, n: int) -> int:
        total = 0
        
        for i in range(1, n + 1):
            total += i
        
        return total
class Solution {
    public int sumOfNaturalNumbers(int n) {
        int sum = 0;
        
        for (int i = 1; i <= n; i++) {
            sum += i;
        }
        
        return sum;
    }
}

Complexity Analysis

Time Complexity: O(n)

The loop runs exactly n times, performing one addition per iteration. Each addition is a constant-time operation, so the total work scales linearly with n.

Space Complexity: O(1)

We use a single integer variable sum to accumulate the result. No arrays, lists, or other data structures are allocated, so space usage is constant regardless of n.

Why This Approach Is Not Efficient

The brute force runs in O(n) time. With the constraint n ≤ 10^4, this is perfectly acceptable for this problem — the loop will run at most 10,000 times, which finishes almost instantly.

However, the iterative approach has a fundamental limitation: the work grows proportionally with n. If we imagined constraints of n ≤ 10^18 (as seen in some competitive programming problems), a loop-based solution would be far too slow — it would take billions of iterations.

More importantly, there exists a closed-form mathematical formula that computes the exact same result in O(1) time — a single arithmetic expression regardless of how large n is. This formula was famously rediscovered by the young mathematician Carl Friedrich Gauss, and understanding it demonstrates a powerful principle: sometimes the best optimization is not a faster algorithm, but a mathematical insight that eliminates the computation entirely.

Optimal Approach - Gauss's Formula

Intuition

There is a famous story about the mathematician Carl Friedrich Gauss. As a young student, his teacher asked the class to add up all numbers from 1 to 100, expecting it to keep them busy. Gauss produced the answer almost immediately.

His insight was elegant: pair up numbers from opposite ends of the range. Consider summing 1 to n:

  • Pair the first and last: 1 + n = (n + 1)
  • Pair the second and second-to-last: 2 + (n - 1) = (n + 1)
  • Pair the third and third-to-last: 3 + (n - 2) = (n + 1)
  • ... and so on.

Every pair sums to exactly (n + 1), and there are n / 2 such pairs. So the total sum is:

Sum = n × (n + 1) / 2

For n = 100: Sum = 100 × 101 / 2 = 5050.

This formula works whether n is even or odd — if n is odd, the middle number pairs with itself in a half-pair, and the arithmetic still holds because one of n or (n + 1) is always even, making the division exact.

We can also prove this formula by mathematical induction:

  • Base case: n = 1: Sum = 1 × 2 / 2 = 1. Correct.
  • Inductive step: Assume the formula holds for n - 1, i.e., Sum(n-1) = (n-1) × n / 2. Then Sum(n) = Sum(n-1) + n = (n-1) × n / 2 + n = (n² - n + 2n) / 2 = n × (n + 1) / 2. Proven.

Step-by-Step Explanation

Let's verify the formula with n = 5:

Step 1: Write down the numbers: 1, 2, 3, 4, 5.

Step 2: Pair from opposite ends:

  • 1 + 5 = 6
  • 2 + 4 = 6
  • 3 is the middle element (unpaired, but the formula handles it)

Step 3: Apply the formula: Sum = n × (n + 1) / 2 = 5 × 6 / 2 = 30 / 2 = 15.

Step 4: Verify against brute force: 1 + 2 + 3 + 4 + 5 = 15. ✓

The formula gives the exact same result as the loop, but in a single computation — no iteration needed.

Let's also verify with n = 10: Sum = 10 × 11 / 2 = 110 / 2 = 55. ✓

Algorithm

  1. Compute sum = n * (n + 1) / 2
  2. Return sum

Code

#include <iostream>
using namespace std;

class Solution {
public:
    int sumOfNaturalNumbers(int n) {
        return n * (n + 1) / 2;
    }
};
class Solution:
    def sumOfNaturalNumbers(self, n: int) -> int:
        return n * (n + 1) // 2
class Solution {
    public int sumOfNaturalNumbers(int n) {
        return n * (n + 1) / 2;
    }
}

Complexity Analysis

Time Complexity: O(1)

The formula involves exactly three arithmetic operations — one multiplication, one addition, and one division — regardless of the value of n. Whether n is 5 or 5 billion, the computation takes the same constant amount of time.

Space Complexity: O(1)

No additional data structures are used. The result is computed directly from the input using a single expression.