Algorithm

problem link- https://www.spoj.com/problems/LOOPEXP/

LOOPEXP - Loop Expectation

#math #probability-theory

 

Consider the following pseudo-code:

int a[1..N];
int max = -1;
for i = 1..N:
    if(a[i] > max):
        max = a[i];

Your task is to calculate the expected number of times the 'if' block of the above pseudo-code executes. The array 'a' is a random permutation of numbers from 1..N chosen uniformly at random.

Input

First line contains t, the number of test cases. t lines follow, each containing N, the number of elements in the array.

1 <= t <= 100

1 <= n <= 100,000

Output

For each test case, output a single decimal. Your answer should be within 10-6 of the correct answer.

Example

Input:
1
2

Output:
1.5

Explanation

For N = 2, you can have the following two permutations: [1, 2] and [2, 1].

In the first case the if block gets executed 2 times, and in the second case the if block gets executed 1 time. So the expected value is (2 + 1) / 2 = 1.5

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

f = [0] * 100001
for i in range (1, 100001):
    f[i] = f[i - 1] + 1 / i

T = int(input())
for i in range(T):
    N = int(input())
    print("%.14f" % f[N])
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
1
2

Output

x
–
+
cmd
1.5
Advertisements

Demonstration

SPOJ Solution-Loop Expectation-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python