Alternating Harmonic Series Sum

Problem

Read n and print 1 - 1/2 + 1/3 - 1/4 + ... (n terms) with 4 digits after the decimal point. The signs change between plus and minus.

Constraints

  • 1 <= n <= 10^6

Examples

Input

10

Output

0.6456

Solutions

Best approachTime O(n)Space O(1)

Odd denominators get a plus sign and even denominators get a minus sign. The remainder operator tells if the denominator is odd. The sum goes to ln(2) = 0.6931 for a large n.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Add the first n terms of the series 1 - 1/2 + 1/3 - 1/4 + ... (n terms).
 * Input   : One integer n (n >= 1).
 * Output  : The sum with 4 digits after the decimal point.
 * Approach: Add the terms one by one with a decimal sum.
 * 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) {
        int n = new Scanner(System.in).nextInt();

        // Step 1: The sum is a decimal number (double). It starts at 0.
        double sum = 0;

        // Step 2: Visit the denominators 1, 2, 3, ... up to n.
        for (int denominator = 1; denominator <= n; denominator++) {
            // Step 3: Use 1.0 and not 1. With 1 / 2 Java would use integer division and give 0.
            if (denominator % 2 == 1) {
                sum = sum + 1.0 / denominator;
            } else {
                sum = sum - 1.0 / denominator;
            }
        }

        // Step 4: Print the sum with 4 digits after the decimal point. Locale.US gives a dot as the separator.
        System.out.println(String.format(Locale.US, "%.4f", sum));
    }
}
Hints (2)
  1. What is 1 / 2 in integer division?
  2. Make the division use decimal numbers.