Sum of First N Natural Numbers
Last Updated: June 7, 2026
Understanding the Problem
Add up every whole number from 1 through n inclusive. For n = 5, that means 1 + 2 + 3 + 4 + 5, which comes to 15.
The edge case is n = 0. There are no numbers to add, so the sum is 0, and a correct solution returns 0 there.
Key Constraints:
ncan be 0 → The sum of an empty range is 0. A loop that never executes leaves the total at 0, and the formula0*(0+1)/2also evaluates to 0, so both methods cover this case naturally.0 <= n <= 10000→ The largest possible result is the sum up to 10000, which is 50,005,000. That fits in a 32-bit signed integer, so a plainintreturn type is safe.- Larger ranges → If
nwere allowed to grow past this limit, the running total could exceed the range of a 32-bit integer. A 64-bit type would then be needed to hold the result without overflow.
Approach 1: Loop and Accumulate
Intuition
Start a running total at 0, then add each integer from 1 to n one at a time. After the loop finishes, the total holds the answer. There is no formula to recall, and the logic is easy to verify by stepping through a small input.
Algorithm
- Initialize a variable
totalto 0. - Loop
ifrom 1 toninclusive. - Add
itototalon each iteration. - After the loop, return
total.
Example Walkthrough
Input:
Starting with total = 0, the loop adds each value in turn. After adding 1 the total is 1, after adding 2 it is 3, after 3 it is 6, after 4 it is 10, and after 5 it is 15. The loop ends and the final total is 15.
Code
- Time Complexity: O(n). The loop runs
ntimes, performing one addition per iteration. - Space Complexity: O(1). Only the running total is stored, regardless of the size of
n.
Approach 2: Gauss Formula
Intuition
A closed-form expression removes the loop entirely. Pair the smallest number with the largest, 1 + n, then the next pair, 2 + (n - 1), and so on. Each pair adds up to n + 1, and there are n / 2 such pairs, so the total is n * (n + 1) / 2. The formula always produces a whole number, because one of n and n + 1 is even, so the division by 2 leaves no fraction.
One detail matters at large n. The product n * (n + 1) can grow larger than the final result before the division happens. Computing that product as a 64-bit long before dividing avoids an intermediate overflow, then the result is narrowed back to the return type.
Algorithm
- Compute the product
n * (n + 1)using a 64-bit type to hold the intermediate value. - Divide the product by 2.
- Return the result.
Example Walkthrough
Input:
With n = 10, the product n * (n + 1) is 10 * 11, which equals 110. Dividing 110 by 2 gives 55. The pairing view confirms this: 1 + 10, 2 + 9, 3 + 8, 4 + 7, and 5 + 6 are five pairs that each sum to 11, and 5 * 11 is 55.
Code
- Time Complexity: O(1). One multiplication, one addition, and one division run in constant time regardless of
n. - Space Complexity: O(1). Only a single intermediate product is stored.