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
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.
/*
* 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)
- What is 1 / 2 in integer division?
- Make the division use decimal numbers.