Arithmetic Progression: N-th Term and Sum

Problem

An arithmetic progression (AP) starts with a number a and adds the same number d to get each next term: a, a + d, a + 2d, ... Read a, d and n. Print the n-th term and the sum of the first n terms.

Constraints

  • 1 <= n <= 10^6, values fit in a 64-bit integer

Examples

Input

2 3 5

Output

N-th term: 14
Sum: 40

Solutions

Best approachTime O(1)Space O(1)

The n-th term is a + (n - 1) * d. The terms form pairs (first + last, second + second-last, ...) that all have the same sum, so the total is (first + last) * n / 2.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Find the n-th term and the sum of the first n terms of an arithmetic progression.
 * Input   : Three integers on one line: first term a, common difference d, count n (n >= 1).
 * Output  : Two lines: N-th term and Sum.
 * Approach: Use the formulas a + (n - 1) * d and n * (2a + (n - 1) * d) / 2.
 * Time    : O(1)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long first = scanner.nextLong();
        long difference = scanner.nextLong();
        long count = scanner.nextLong();

        // Step 1: The n-th term is the first term plus (n - 1) times the difference. Example: 2 + 4 * 3 = 14.
        long lastTerm = first + (count - 1) * difference;

        // Step 2: The sum is (first term + last term) times n, divided by 2. The product is always even, so the division is exact.
        long sum = (first + lastTerm) * count / 2;

        // Step 3: Print both results.
        System.out.println("N-th term: " + lastTerm);
        System.out.println("Sum: " + sum);
    }
}
Hints (2)
  1. How many steps of size d do you take to reach the n-th term?
  2. Pair the first and the last term.