1.
Problem
1.1.
Example -
2.
Approach
3.
Implementation
3.1.
Output
4.
Time Complexity: O(N^2)
4.1.
Space Complexity: O(1)
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

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

## Problem

Given two integers ‘N’ and ‘M’, representing the total number of boys and girls respectively, you have to find the number of ways to form a team of size ‘K’, containing at least 4 boys and at least 1 girl.

Constraints:

4 <= N <= 25

1 <= M <= 25

5 <= K <= N + M.

#### Example -

Input: N = 5, M = 3, K = 6

Output: 18

Explanation:

The total size of the team is 6, which means we can either choose 4 boys and 2 girls or 5 boys and 1 girl.

1. Number of ways to choose 4 boys out of 5 is 5C4 = 5, and the number of ways to choose 2 girls out of 3 is 3C2 = 3. Therefore, the number of ways to form a team of 4 boys and 2 girls is 5 * 3 = 15.
2. Number of ways to choose 5 boys out of 5 is 5C5 = 1, and the number of ways to choose 1 girl out of 3 is 3C1 = 3. Therefore, the number of ways to form a team of 5 boys and 1 girl is 1 * 3 = 3.

Therefore, the total number of ways to form a team of size 6 is 15 + 3 = 18.

Input: N = 6, M = 4, K = 7

Output: 100

Also see, Euclid GCD Algorithm

## Approach

Prerequisite - Combinations

For a fixed size K, let us say we can form a team (i, j) where ‘i’ denotes the number of boys, and ‘j’ denotes the number of girls in the team. The following are the constraints on (i, j):

1. i + j = K
2. 4 <= i <= N
3. 1 <= j <= M

From the first equation, we get:

j = K - i

By substitutiog it in third equation, we get:

1 <= K - i <= M

Therefore, we need to form a team of size (i, K - i) if the following conditions hold:

1. 4 <= i <= N
2. 1<= K - i <= M

Now we can iterate over the ‘i’ to find the composition of the teams that we can form. We can calculate the number of teams to form a team of a particular composition (i, j) by -

NCiMCj

To calculate the number of ways to form a team, we can add the answer over all the valid i and j.

## 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){

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;

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.

Live masterclass