# 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 1 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! Follow us on Instagram @programmersdoor 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