## Problem Link:

```
<a href = "https://www.codechef.com/NOV18B/problems/MAGICHF2"> Contest </a>
<b>Author</b>: <a href="https://www.codechef.com/users/shivam_g1470">shivam_g1470</a>
<b>Editorialist</b>: <a href="https://www.codechef.com/users/srvptk">srvptk</a>
```

## Difficulty: Easy

## Prerequisites: Divide and Conquer, Recursion, Maths

## Problem:

Chef has **N** coins out of which **1** is real and other **(N-1)** coins are fake. He has to find the maximum probability in worst

case to determine the real coin with the help of a balance by using it upto **K** times.

## Explanation:

This problem can be solved through a divide and conquer approach. Everytime we have **N** coins, we will be dividing it into

two approximately equal halves and process the larger one. When we divide the **N** coins into two halves then we can use the

balance to determine whether the coin is in one of the halves. If we checked either of the half for a real coin and failed then we

will continue our search with other half, otherwise we would search the checked half.

As we are interested in the worst case scenario, so we would always go with the larger half.

By this approach our problem can be solved in **logN** time, which can successfully be applied for **N**<=**10^18**.

When we can no longer use the balance then we have to select one of the coin to be real from the remaining part left unsearched, and the

probability of finding a real coin will be: **1/(no. of remaining coins)**

### Recursive Approach:

```
<b>double Compute(N,k)</b>{
if(k>=N){
return 1.0
}
if(k==0){
return 1.0/(double)N
}
hlf1 = N/2
hlf2 = (N-hlf1)
return Compute( max(hlf1,hlf2), k-1)
```

}

### Corner Cases:

Now we have to deal with some corner cases. My solution had to deal with three corner cases, these were:-
if
**N**=**1**`<b>result = 1.0</b> </li> <li> if <b>N</b>=<b>2</b> <b>result = 0.5</b> Doesn't matter how many times we use the balance, we won't be able to find the real coin among the two. So, the probability of finding a real coin will always be <b>0.5</b> irrespective of the value of <b>K</b>. </li> <li> if <b>K</b>=<b>1</b> If both hlaves are odd then we have to deal with <b>max(hlf1,hlf2)+1</b> coins in total (Observation). So, <b>result = 1.0/(max(hlf1,hlf2)+1)</b> Otherwise, <b>result = 1.0/max(hlf1,hlf2) </b> </li> <li> If we don't get into any of the above corner cases, we simply use: <b> Compute(N,K) </b> </li>`

**O(logN)**for every case. ## Implementation: Editorialist Solution