Choose Students

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
7 upvotes
Asked in company
D.E.Shaw

Problem statement

You are the teacher of a class and you have N students in the class. You are asked to choose R students from your class for a competition. All your students are equally competent. Find the number of ways you can choose R students from a class of N students.

Note : Number of ways of choosing 0 students from N students is 1.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

Then the T test cases follow.

The first line of each test case contains two space separated integers ‘N’ and ‘R’ denoting the total number of students in the class and number of students to choose respectively.

Output format:

For each test case, the number of ways to choose R students out of N is printed.
The output of each test case is printed in a separate line.
Constraints : 
1 <= T <= 10
1 <= N <= 200
0 <= R <= N
where ‘T’ is the number of test cases, ‘N’ is the total number of students in the class and ‘R’ is the number of students to choose.

Sample Input 1:

1
3 2

Sample Output 1:

3

Explanation of Sample Input 1:

Ways to choose 2 students from 3 : {1,2}, {1,3}, {2,3}.

Sample Input 2:

3
4 1
5 5
3 0

Sample Output 2:

4
1
1
Hint

The above statement is a very common mathematics problem and is solved using Binomial Coefficient. The binomial coefficients are the positive integers that occur as coefficients in the binomial theorem.

Approaches (3)
Brute Force approach

The idea is to recursively find the value of C(N, R). Using the standard formula of calculating Binomial Coefficient.

C(N,R) = C(N-1, R-1) + C(N-1, R).

C(N, 0) = C(N, N) = 1

Starting form a total of N students there will be two cases of choosing R students :

  1. Include the last student in the chosen students, so now R-1 students are to be chosen from N-1 students. That is C(N-1, R-1).
  2. Do not include the last student in the chosen students, so R students are to be chosen from N-1 students. That is C(N-1, R).

Algorithm: 

  • Recursive Function: chooseHelper(N, R).
  • Base conditions :
    • if R > N , return 0
    • If R = 0 or R = N, return 1.
  • There will be two cases : Recursively find the value of chooseHelper(N-1, R-1) and chooseHelper(N-1, R).
  • Return the sum of above two values.
Time Complexity

O(2^N), where ‘N’ is the total number of students in class.

 

The maximum size of the recursion tree can go upto 2^N. As for every student there are two options, whether to choose it or not and that leads to O(2*2*2….N terms). Thus, the final time complexity is O(2^N).

Space Complexity

O(N), where ‘N’ is the total number of students in class.

 

We are using recursion and O(N) space will be taken by the recursion stack. Thus, the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Choose Students
Full screen
Console