Sum of the First N Natural Numbers
Solve this ProblemEasy5–10 min
Topics
BasicsLoopsMath
Companies
TCSInfosysWipro
Given a non-negative integer
n, return the sum 1 + 2 + 3 + ... + n.
The loopAddition LoopWalking i from 1 to n, adding each value to a running total. version is the direct reading of what "sum of the first n numbers" means. Gauss's formulaGauss's Formulan × (n + 1) / 2 — pairing the smallest and largest remaining numbers (1 with n, 2 with n-1, ...), each pair summing to n+1, with n/2 such pairs., famously discovered by Carl Friedrich Gauss as a schoolboy, skips the loop entirely: it's one multiplication and one division, no matter how large n is — a genuine O(1) solution to an O(n)-looking problem.
Test Case 1:
Input:n = 5
Output:15
Explanation:1 + 2 + 3 + 4 + 5 = 15.
Test Case 2:
Input:n = 1
Output:1
Explanation:Just the one number.
Test Case 3:
Input:n = 0
Output:0
Explanation:Nothing to add.
Constraints
- ◆
0 ≤ n ≤ 1000000
Try the Dry Run
Approach & Solutions
Loop — Add Each NumberGood
Walk i from 1 to n, adding each value to a running total. Direct and easy to trust, but it does n additions no matter how large n gets.
Time
O(n)Space
O(1)Java
1class Solution {
2 public long sumOfFirstN(int n) {
3 long sum = 0;
4 for (int i = 1; i <= n; i++) {
5 sum += i;
6 }
7 return sum;
8 }
9}Gauss's Formula — n × (n + 1) / 2Optimal
Pair the numbers from both ends: 1 with n, 2 with (n - 1), 3 with (n - 2), and so on — each pair adds up to exactly (n + 1), and there are n / 2 such pairs, so the total is always n × (n + 1) / 2. No loop at all — just one multiplication and one division, regardless of how large n is.
Time
O(1)Space
O(1)Java
1class Solution {
2 public long sumOfFirstN(int n) {
3 return (long) n * (n + 1) / 2;
4 }
5}