Last Updated: 3 Jan, 2021
Choose Students
Moderate
Asked in company
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.
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.
Approaches
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 :
- 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).
- 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.
C => Binomial Coefficient
As you can see in the figure above, this problem leads to recomputation of the same data again and again.
The idea is the same as the previous approach, but in the previous approach many recursive calls were made again and again with the same parameters. This can be eliminated by storing the value obtained from a particular call in a 2d array, called the memo array. memo[i][j] stores the value of the Binomial Coefficient of C(i,j) that is the number of ways of choosing ‘j’ students from ‘i’ students.
Algorithm:
- An array, memo, of size (N+1)*(R+1) is taken.
- Recursive Function: chooseHelper( N, R, memo).
- Base conditions :
- If memo[N][R] is not -1, return its value.
- If R = 0 or R = N, update memo[N][R] = 1 and return 1.
- There will be two cases : Recursively find the value of chooseHelper(N-1, R-1, memo) and chooseHelper(N-1, R, memo).
- Update the sum of values returned by above recursive calls in memo[N][R]
Rows of pascal triangle :
1==========> n = 0, C(0,0) = 1
1–1========> n = 1, C(1,0) = 1, C(1,1) = 1
1–2–1======> n = 2, C(2,0) = 1, C(2,1) = 2, C(2,2) = 1
1–3–3–1====> n = 3, C(3,0) = 1, C(3,1) = 3, C(3,2) = 3, C(3,3)=1
1–4–6–4–1==> n = 4, C(4,0) = 1, C(4,1) = 4, C(4,2) = 6, C(4,3)=4, C(4,4)=1
As seen above, every loop builds a row of pascal triangle using the previous row of the pascal triangle. The right-hand side represents the value coming from the previous iteration (A row of Pascal’s triangle depends on the previous row). The left-Hand side represents the value of the current iteration which will be obtained.
Algorithm:
- Take an array, pascal, of size ‘R+1’ and initialize all its values with 0.
- pascal[0] = 1
- Compute next rows of the pascal triangle from the previous one using C[j] = C[j] + C[j-1]
- Find all the rows of the pascal triangle from 1 to N.
- Iterate over all the values from 1 to N and for the ith row use the values of (i-1)th row.
That is for every value from min(i,R) to 0, fill the pascal array using the previous values of the pascal array (as those values are for the previous row).
pascal[j] = pascal[j] + pascal[j-1]. - At the end of the above iteration, return the value of pascal[R].