Loading…

easyBasicsSometimes asked

Sum from 1 to N

Basics · 6 min

Given a positive integer n, return the sum 1 + 2 + … + n.

In plain English

You can loop and accumulate, but the closed-form `n(n+1)/2` gives the answer in O(1).

Examples

Example 1

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

Example 2

Input: n = 1
Output: 1
Note: Just 1.

Example 3

Input: n = 100
Output: 5050
Note: Gauss's sum.

Constraints

1 ≤ n ≤ 10^9

Clarifying questions2First question: How large can n be?Explore questions

Q1.How large can n be?
Up to ~10⁹, which is why the product needs a 64-bit type.
Q2.Is n always positive?
Yes; the formula assumes n ≥ 1 (n = 0 would give 0).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Use the formula `n * (n + 1) / 2`. It's O(1) and beats the O(n) loop. Use a 64-bit type because `n(n+1)` overflows int for large n.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you replace an O(n) loop with a closed form and guard the multiplication against overflow.

Where candidates slip

Returning a wrapped negative for large n due to int overflow in n*(n+1).

How to stand out

Derive the formula via Gauss pairing and explain why /2 is exact.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Gauss formula

TimeO(1)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A loop works, but can you find the answer without iterating?

2Hint 2Explore hint

Pair the first and last terms: 1+n, 2+(n−1)… each pair sums to n+1.

3Hint 3Explore hint

Use n(n+1)/2 — and widen to 64-bit before multiplying for large n.

A · Core idea

You can add 1 + 2 + … + n with a loop in O(n), but the closed form n(n+1)/2 gives the same answer in O(1). Recognising when a loop collapses into a formula is the lesson.

Why the formula works (Gauss's pairing). Write the sum forwards and backwards and add term by term: (1+n) + (2+(n−1)) + … Each of the n pairs sums to n+1, and there are n of them, giving n(n+1) for twice the sum — so the sum itself is n(n+1)/2. The young Gauss reputedly used this to add 1..100 = 5050 in seconds.

Why `/2` is always exact. Among any two consecutive integers n and n+1, exactly one is even, so their product is always divisible by 2 — the integer division loses nothing.

The overflow detail. For n near 10⁹, n * (n + 1) is near 10¹⁸, which overflows 32-bit int long before the divide. Widen to long before multiplying — (long) n * (n + 1) / 2. This 'compute big, then divide' ordering is a recurring interview trap.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5

pair ends

(1+5)+(2+4) and the middle 3

Statethree pairs of 6 = sum*2

Final result15

C · Code with teaching comments

solution.javaJava

Gauss formula — optimal

1 teaching note

1
public long sumToN(int n) {
2
    // Cast to long first so n*(n+1) doesn't overflow int.
3
    return (long) n * (n + 1) / 2;
4
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.4 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

Mention the O(n) loop, then upgrade to the formula and flag the overflow — that progression is exactly what interviewers want to hear.

ComplexityO(1) time, O(1) space — the closed form is a fixed handful of arithmetic operations regardless of n.

E · Edge cases and pitfalls4n = 1 — 1 * 2 / 2 = 1, the single term.Explore edge cases

Edge cases handled

n = 11 * 2 / 2 = 1, the single term.
n = 1000000000≈5×10¹⁷ — fits in long, overflows int; the cast is essential.

Pitfalls

Computing `n * (n + 1)` in int and overflowing before the divide.
Dividing before multiplying and losing the factor of 2 (only safe because one factor is even — keep the /2 last).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long sumToN(int n) { return (long) n * (n + 1) / 2; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Computing `n*(n+1)` in int and overflowing.
Using integer division before multiplication and losing precision.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Closed-form sum

Code pattern to memorize

return (long) n * (n + 1) / 2;

Rules to remember

1n(n+1)/2.
2Widen to long before multiplying.
3One of the two consecutive factors is always even, so /2 is exact.

Use this pattern when

Summing a contiguous arithmetic range
Replacing a counting loop with a closed form

Choose another pattern when

The series isn't arithmetic — no closed form, just loop

Interview takeaway

A known closed form turns an O(n) loop into O(1).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Closed-form sum. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

easyBasicsSometimes asked

Sum from 1 to N

Basics · 6 min

Given a positive integer n, return the sum 1 + 2 + … + n.

In plain English

You can loop and accumulate, but the closed-form `n(n+1)/2` gives the answer in O(1).

Examples

Example 1

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

Example 2

Input: n = 1
Output: 1
Note: Just 1.

Example 3

Input: n = 100
Output: 5050
Note: Gauss's sum.

Constraints

1 ≤ n ≤ 10^9

Clarifying questions2First question: How large can n be?Explore questions

Q1.How large can n be?
Up to ~10⁹, which is why the product needs a 64-bit type.
Q2.Is n always positive?
Yes; the formula assumes n ≥ 1 (n = 0 would give 0).

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Use the formula `n * (n + 1) / 2`. It's O(1) and beats the O(n) loop. Use a 64-bit type because `n(n+1)` overflows int for large n.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you replace an O(n) loop with a closed form and guard the multiplication against overflow.

Where candidates slip

Returning a wrapped negative for large n due to int overflow in n*(n+1).

How to stand out

Derive the formula via Gauss pairing and explain why /2 is exact.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Gauss formula

TimeO(1)SpaceO(1)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A loop works, but can you find the answer without iterating?

2Hint 2Explore hint

Pair the first and last terms: 1+n, 2+(n−1)… each pair sums to n+1.

3Hint 3Explore hint

Use n(n+1)/2 — and widen to 64-bit before multiplying for large n.

A · Core idea

You can add 1 + 2 + … + n with a loop in O(n), but the closed form n(n+1)/2 gives the same answer in O(1). Recognising when a loop collapses into a formula is the lesson.

Why `/2` is always exact. Among any two consecutive integers n and n+1, exactly one is even, so their product is always divisible by 2 — the integer division loses nothing.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5

pair ends

(1+5)+(2+4) and the middle 3

Statethree pairs of 6 = sum*2

Final result15

C · Code with teaching comments

solution.javaJava

Gauss formula — optimal

1 teaching note

1
public long sumToN(int n) {
2
    // Cast to long first so n*(n+1) doesn't overflow int.
3
    return (long) n * (n + 1) / 2;
4
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.4 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

Mention the O(n) loop, then upgrade to the formula and flag the overflow — that progression is exactly what interviewers want to hear.

ComplexityO(1) time, O(1) space — the closed form is a fixed handful of arithmetic operations regardless of n.

E · Edge cases and pitfalls4n = 1 — 1 * 2 / 2 = 1, the single term.Explore edge cases

Edge cases handled

n = 11 * 2 / 2 = 1, the single term.
n = 1000000000≈5×10¹⁷ — fits in long, overflows int; the cast is essential.

Pitfalls

Computing `n * (n + 1)` in int and overflowing before the divide.
Dividing before multiplying and losing the factor of 2 (only safe because one factor is even — keep the /2 last).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long sumToN(int n) { return (long) n * (n + 1) / 2; }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Computing `n*(n+1)` in int and overflowing.
Using integer division before multiplication and losing precision.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Closed-form sum

Code pattern to memorize

return (long) n * (n + 1) / 2;

Rules to remember

1n(n+1)/2.
2Widen to long before multiplying.
3One of the two consecutive factors is always even, so /2 is exact.

Use this pattern when

Summing a contiguous arithmetic range
Replacing a counting loop with a closed form

Choose another pattern when

The series isn't arithmetic — no closed form, just loop

Interview takeaway

A known closed form turns an O(n) loop into O(1).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Closed-form sum. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern