Exponential Series e^x

medium Series and Sequences

Problem

Read a decimal number x and a count n. Print the sum of the first n terms of 1 + x/1! + x^2/2! + x^3/3! + ... with 4 digits after the decimal point. This sum is an estimate of e^x.

Constraints

  • -10 <= x <= 10, 1 <= n <= 100

Examples

Input

1 10

Output

2.7183

Solutions

Best approachTime O(n)Space O(1)

Each term is the previous term multiplied by x and divided by k. We never calculate a power or a factorial directly, so the numbers stay small and the code is fast.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Estimate e^x with the first n terms of 1 + x + x^2/2! + x^3/3! + ...
 * Input   : A decimal number x and an integer n on one line.
 * Output  : The estimate with 4 digits after the decimal point.
 * Approach: Calculate each term from the previous term: term = term * x / k.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Locale;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // Locale.US makes the scanner read a dot as the decimal separator.
        Scanner scanner = new Scanner(System.in).useLocale(Locale.US);
        double x = scanner.nextDouble();
        int count = scanner.nextInt();

        // Step 1: The first term is 1 (x to the power 0 divided by 0!). The sum starts with it.
        double term = 1.0;
        double sum = 1.0;

        // Step 2: Calculate the next terms. Term k is the previous term times x divided by k.
        for (int k = 1; k < count; k++) {
            // Step 3: This avoids big powers and big factorials. Example: x^3 / 3! = (x^2 / 2!) * x / 3.
            term = term * x / k;
            sum = sum + term;
        }

        // Step 4: Print the sum with 4 digits after the decimal point.
        System.out.println(String.format(Locale.US, "%.4f", sum));
    }
}
Hints (2)
  1. How do you get x^3 / 3! from x^2 / 2!?
  2. Which value is the first term?