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.
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.
1
3 2
3
Ways to choose 2 students from 3 : {1,2}, {1,3}, {2,3}.
3
4 1
5 5
3 0
4
1
1
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.
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 :
Algorithm:
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).
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).
All tags
Sort by
Interview problems
Choose Students || C++ Solution
#include <bits/stdc++.h>
using namespace std;
int choose(int n, int r){
if (r == 0 || r == n) {
return 1;
}
// Using dynamic programming to calculate combination
vector<vector<int>> dp(n + 1, vector<int>(r + 1, 0));
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= min(i, r); ++j) {
if (j == 0 || j == i) {
dp[i][j] = 1;
} else {
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]);
}
}
}
return dp[n][r];
}
Interview problems
3 - Liner | DP
#include <bits/stdc++.h>
int choose(int n, int r){
int res = 1;
for(int i=1;i<=r;i++){
res = (res * (n-i+1)) / i;
}
return res;
}
Interview problems
python solution
from os import *
from sys import *
from collections import *
from math import *
from math import factorial
def choose(n, r):
return factorial(n) // (factorial(r) * factorial(n - r))
pass
Interview problems
A pure mathematical problem where nCr is used ..
import java.util.* ;
import java.io.*;
public class Solution {
static long fact(long r)
{
if(r==1)
return 1;
return r*fact(r-1);
}
public static int choose(int n, int r) {
// Write your code here.
/* pure mathematical problem.....
Here selection so combination problem
===> nCr = n!/(n-r)!*r!
this could be simplified as
(n * n-1 * n-2 * .... n-r+1) / r!
hence answer calculated .
edge cases
if r==0 return 1
if r>=n return 1 // since only one combinarion can be selected in both the cases...
*/
if(r==0)
return 1;
if(r>=n)
return 1;
long Numerator= 1 ;
for(int i=n;i>=(n-r+1);i--)
{ Numerator =Numerator * i; }
long denominator =fact(r);
return (int) (Numerator/denominator);
}
}
Discussion thread on Interview Problem | Choose Students
Hey everyone, creating this thread to discuss the interview problem - Choose Students.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Choose Students
