Sum of the First N Numbers

beginner Programming Basics

Problem

Read n and print the sum of the numbers from 1 to n. For n = 0 the sum is 0.

Constraints

  • 0 <= n <= 10^9

Examples

Input

5

Output

15

Solutions

Brute forceTime O(n)Space O(1)

The loop adds the numbers one by one into an accumulator variable.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Find the sum 1 + 2 + ... + n.
 * Input   : One integer n (n >= 0).
 * Output  : The sum.
 * Approach: Add the numbers in a loop.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();

        // Step 1: The sum starts at 0. We use long, because the sum can be larger than an int.
        long sum = 0;

        // Step 2: Visit every number from 1 to n and add it to the sum.
        for (int number = 1; number <= n; number++) {
            sum = sum + number;
        }

        // Step 3: Print the sum.
        System.out.println(sum);
    }
}
Hints (1)
  1. Start the sum with 0.