Geometric Progression: N-th Term and Sum

Problem

A geometric progression (GP) starts with a number a and multiplies by the same number r to get each next term: a, a * r, a * r * r, ... Read a, r and n. Print the n-th term and the sum of the first n terms.

Constraints

  • 1 <= n <= 20, the n-th term fits in 53 bits

Examples

Input

2 3 5

Output

N-th term: 162
Sum: 242

Solutions

Best approachTime O(n)Space O(1)

Each term is the previous term times r. The loop adds every term. It works for every ratio, including r = 1.

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 a geometric progression.
 * Input   : Three integers on one line: first term a, common ratio r, count n (n >= 1).
 * Output  : Two lines: N-th term and Sum.
 * Approach: Multiply the term by r in a loop and add each term to the sum.
 * Time    : O(n)
 * 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 ratio = scanner.nextLong();
        long count = scanner.nextLong();

        // Step 1: Start with the first term. The sum is 0 before we add any term.
        long term = first;
        long sum = 0;

        // Step 2: Repeat n times: add the current term to the sum, then calculate the next term.
        for (long step = 1; step <= count; step++) {
            sum = sum + term;
            if (step < count) {
                term = term * ratio;
            }
        }

        // Step 3: Print both results. "term" is the n-th term now.
        // The loop also works when the ratio is 1, where the usual sum formula would divide by zero.
        System.out.println("N-th term: " + term);
        System.out.println("Sum: " + sum);
    }
}
Hints (1)
  1. What happens to the sum formula when r = 1?