Prateek Chauhan
- Jun 24, 2020
- 2 min read

TCS Codevita | Lazy Student

In this blog, we will discuss a problem asked in TCS Codevita 2019.

Before running into the solution try it by yourself first.

Problem Description

There is a test of Algorithms. The teacher provides a question bank consisting of N questions and guarantees all the questions in the test will be from this question bank. Due to lack of time and his laziness, Codu could only practice M questions. There are T questions in a question paper selected randomly. Passing criteria is solving at least 1 of the T problems. Codu can't solve the question he didn't practice. What is the probability that Codu will pass the test?

Constraints

0 < T <= 10000
0 < N, T <= 1000
0 <= M <= 1000
M,T <= N

Input Format

First-line contains single integer T denoting the number of test cases.

The first line of each test case contains 3 integers separated by space denoting N, T, and M.

Output

For each test case, print a single integer.

If the probability is p/q where p & q are co-prime, print (p*mulInv(q)) modulo 1000000007, where mulInv(x) is the multiplicative inverse of x under modulo 1000000007.

Timeout

Test Case

Example 1

Input

1
4 2 1

Output

500000004

Explanation

The probability is ½. So the output is 500000004.

Implementation using C:

#include<stdio.h>
 int combinations(int n, int r)
{
    int itr;
    int numerator=1,denominator=1,result;
    for(itr=1; itr<=r; itr++)
    {
        denominator = denominator*itr;
        numerator = numerator*(n-(itr-1));
    }
    result = numerator/denominator;
    return result;
}

int calcGCD( int num1, int num2)
{
    int rem;
    while(1)
    {
        rem = num1%num2;
        if(rem==0)
            return num2;
        if(rem!=0)
        {
            num1=num2;
            num2 = rem;
        }
    }
}
long long int mulInv(long long int a)
{
    long long int m =1000000007,itr,b;
    for(itr=1; itr<m; itr++)
    {
        if((itr*m+1)%a==0)
        {
            b = (itr*m+1)/a;
            break;
        }
    }
    return b;
}

int main()
{
    int t,itr;
    scanf("%d",&t);
    for(itr=1; itr<=t; itr++)
    {
        int qb_questions, learnt, chosen, unknown, gcd;
      long long int result;
        int waysOfChoosing,waysOfFailing,p,q;
        scanf("%d %d %d",&qb_questions,&learnt,&chosen);
        unknown = qb_questions-learnt;
        waysOfChoosing = combinations(qb_questions,chosen);
        waysOfFailing = combinations(unknown,chosen);
        p = waysOfChoosing-waysOfFailing;
        q = waysOfChoosing;
        gcd = calcGCD(p,q);
        if(gcd!=1)
        {
            p = p/gcd;
            q = q/gcd;
        }
        result = (p*mulInv(q))%1000000007;
        printf("%lld",result);
        return 0;
    }
}

Happy Coding!

Join us on Telegram @programmersdoor

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science