Number Of Ways To Form A Team Of Size K Having At Least 4 Boys And 1 Girl.

Implementation

#include<bits/stdc++.h>
#define ll long long
using namespace std;

// Function to compute nCr
ll ncr(ll n, ll r){
    ll num = 1, den = 1;
    for (ll i=0; i<r; i++){
        num *= (n-i);
        den *= (i+1);
    }
    return num/den;
}

/*
Function to find the  
Number of ways to form a team.
*/
void solve(ll n, ll m, ll k){

    // Initializing answer
    ll ans = 0;

    // Iterating over the number of boys
    for(ll i=4; i<=n; i++){

        // If k - i is less than 1, break
        if (k-i < 1) break;

        // Else update the answer.
        ans += ncr(n,i) * ncr(m, k-i);
    }

    // Printing the number of ways to form a team.
    cout<<ans<<endl;
}

// Driver Code
int main(){
    ll n = 5, m = 3, k = 6;
    solve(n,m,k);
    return 0;
}

Output

18

Time Complexity: O(N^2)

We are iterating over the number of boys from 4 till N, and then for each iteration, we are the number of ways to form a team (i, K-i) using nCr. This will also take O(N) time in the worst case. Therefore the total time complexity of the above approach is O(N^2). However, we can improve it using faster ways to compute nCr, but that is not required in this problem.

Space Complexity: O(1)

We have just created some extra variables to calculate our answer. Therefore the space complexity of the above approach is O(1).

FAQs

1. Where is Combination used?
   Combinations are used when we have to select a group of something without considering the order in which we select them or their arrangement.
    
2. How to efficiently compute nCr % p?
   We can compute nCr % p efficiently by using Fermat Little Theorem by using precomputation of the factorial and modular inverse. 
   The final formula is : nCr % p = (fac[n]* modIverse(fac[r]) % p * (fac[n-r]) % p) % p.

Key Takeaways

This article discussed finding the number of ways to form a team of size K having at least 4 boys and at least 1 girl. We also discussed the time and space complexity of our solution. If you want to solve more such problems, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.

Until then, All the best for your future endeavors, and Keep Coding.