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?


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.


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.



Test Case

Example 1


4 2 1




The probability is ½. So the output is 500000004.

Implementation using C:

 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;
        rem = num1%num2;
            return num2;
            num2 = rem;
long long int mulInv(long long int a)
    long long int m =1000000007,itr,b;
    for(itr=1; itr<m; itr++)
            b = (itr*m+1)/a;
    return b;

int main()
    int t,itr;
    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);
            p = p/gcd;
            q = q/gcd;
        result = (p*mulInv(q))%1000000007;
        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

889 views0 comments

        Contact Us

  • LinkedIn
  • Facebook
  • Instagram

©2023 by Programmers Door