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
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.
/*
* 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)
- How many steps of size d do you take to reach the n-th term?
- Pair the first and the last term.