Code Logo

Sum of Natural Numbers

Published at25 Jul 2026
Created by
Basic Operations Easy 3 views
Like0

Given a non-negative integer n, compute the sum of all natural numbers from 1 to n inclusive. The formula is: sum = 1 + 2 + 3 + ... + n = n × (n + 1) / 2.

For example, the sum of numbers from 1 to 5 is 1 + 2 + 3 + 4 + 5 = 15. Using the formula: 5 × 6 / 2 = 30 / 2 = 15. For n = 0, the sum is 0. For n = 1, the sum is 1.

This problem introduces the concept of arithmetic series and the famous formula attributed to Carl Friedrich Gauss. Legend has it that young Gauss discovered this formula when his teacher asked the class to sum the numbers from 1 to 100 — Gauss recognized the pattern and solved it instantly. The formula is used extensively in algorithm analysis (summation of O(n) operations), combinatorics, and series calculations.

A naive implementation would use a loop to accumulate the sum, which runs in O(n) time. The formula approach runs in O(1) time and is preferable for efficiency, especially for large n. The formula n × (n + 1) / 2 works for all non-negative n, including n = 0 where the result is 0.

When implementing the formula, be careful with integer overflow: n × (n + 1) can overflow for large n before the division by 2 brings the result back into range. For the constraints of this challenge, standard 32-bit integers are sufficient.

Example Input & Output

Example 1
Input
10
Output
55
Explanation

1+2+...+10=55

Example 2
Input
3
Output
6
Explanation

1+2+3=6

Example 3
Input
5
Output
15
Explanation

1+2+3+4+5=15

Example 4
Input
0
Output
0
Explanation

Empty sum

Example 5
Input
1
Output
1
Explanation

Just 1

Algorithm Flow

Recommendation Algorithm Flow for Sum of Natural Numbers

Solution Approach

Use the arithmetic series formula n * (n + 1) / 2 for an O(1) solution.

function solution(n) {
  return n * (n + 1) / 2;
}

The formula n * (n + 1) / 2 computes the sum directly without iteration. For n = 5: 5 * 6 / 2 = 30 / 2 = 15. For n = 0: 0 * 1 / 2 = 0. The integer division truncates correctly because either n or n + 1 is always even, so the product is always divisible by 2.

A loop-based alternative is also valid but runs in O(n) time:

function solution(n) {
  var sum = 0;
  for (var i = 1; i <= n; i++) sum += i;
  return sum;
}

The formula approach is preferred for its constant-time performance. Time complexity is O(1), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int n) {return n*(n+1)/2;}
}