Expected move with Solution

Expected move:

Problem Description:

You are given a fair coin and two integers X and N.

You repeatedly flip the coin and perform the following operation based on the result:

·       If it lands on heads, then X will increase by 1. However, if X=N then X will not change.

·       If it lands on tails, X will decrease by 1.

You stop as soon as the value of X becomes 1.

Find the expected number of coin flips.

Note that it is guaranteed that under the given constraints, the answer is an integer and does not exceed 2⋅10^18

Input:

·       The first line contains a single integer T — the number of test cases. Then the test cases follow.

·       The first and only line of each test case contains two space-separated integers X and N.

Output:

For each testcase, output the expected number of coin flips.

Constraints

·       1≤T≤10^5

·       1≤X≤N≤10^9

Sample Input 1:

4

1 3

2 2

12 12

568 57800

Sample Output 1:

0

2

132

65223144

EXPLANATION:

In the first test case, X is already 1. So, the expected number of the coin flips, in this case, is 0.

In the second test case, if the coin lands on the head, X will not change because X is equal to N. Whenever the coin lands on the tail, X will decrease by 1 and the game ends as X becomes 1. The expected number of coin flips to get the first tail is 2. So, the answer for the case is 2.

Solution:

C++:

#include <iostream>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        unsigned long long int x, n, moves = 0;
        cin >> x >> n;
        moves = (x - 1) * (2 * n - x);
        cout << moves << endl;
    }
    return 0;
}

Don't forget to share this post.