Saturday, January 11, 2025
Google search engine
HomeData Modelling & AICount of Ways to Choose N People Containing at Least 4 Boys...

Count of Ways to Choose N People Containing at Least 4 Boys and 1 Girl from P Boys and Q Girls | Set 2

Given integers N, P, and Q the task is to find the number of ways to form a group of N people having at least 4 boys and 1 girl from P boys and Q girls.

Examples:

Input:  P = 5, Q = 2, N = 5
Output: 10
Explanation:  Suppose given pool is {m1, m2, m3, m4, m5} and {w1, w2}. Then possible combinations are:
m1 m2 m3 m4 w1
m2 m3 m4 m5 w1
m1 m3 m4 m5 w1
m1 m2 m4 m5 w1
m1 m2 m3 m5 w1
m1 m2 m3 m4 w2
m2 m3 m4 m5 w2
m1 m3 m4 m5 w2
m1 m2 m4 m5 w2
m1 m2 m3 m5 w2

Hence the count is 10.

Input:  P = 5, Q = 2, N = 6
Output: 7

 

Naive Approach: This problem is based on combinatorics, and details of the Naive approach is already discussed in Set-1 of this problem. 

For some general value of P, Q and N we can calculate the total possible ways using the following formula:

_{4}^{P}\textrm{C} \ast _{N-4}^{Q}\textrm{C} + _{5}^{P}\textrm{C} \ast _{N-5}^{Q}\textrm{C} + . . . + _{N-2}^{P}\textrm{C} \ast _{2}^{Q}\textrm{C} + _{N-1}^{P}\textrm{C} \ast _{1}^{Q}\textrm{C}

where 

_{r}^{n}\textrm{C} = \frac{n!}{r!*(n-r)!}

In this approach at every step we were calculating the value for each possible way.
Time Complexity: O(N2)
Auxiliary Space: O(1)

Efficient Approach: To solve this problem efficiently, we can use the Pascal Triangle property to calculate the _{r}^{n}\textrm{C}         , i.e.

1
1 1
1 2 1
1 3 3 1
.
.
.

which is nothing but

_{0}^{0}\textrm{C}
_{0}^{1}\textrm{C}           _{1}^{1}\textrm{C}
_{0}^{2}\textrm{C}           _{1}^{2}\textrm{C}           _{2}^{2}\textrm{C}
_{0}^{3}\textrm{C}           _{1}^{3}\textrm{C}           _{2}^{3}\textrm{C}           _{3}^{3}\textrm{C}
.
.
.

Follow the steps mentioned below:

  • Use the pascal triangle to precalculate the values of the combination.
  • Start iterating a loop from i = 4 to i = P and do the following for each iteration.
  • Check if (N-i) ≥ 1 and (N-i) ≤ Q.
  • If the condition is satisfied then count the possible ways for i men and (N-i) women, otherwise, skip the step.
  • Add the count with the total number of ways.
  • Return the total count as your answer.

Below is the implementation of the approach:

C++




#include <bits/stdc++.h>
using namespace std;
 
long long int pascal[31][31];
 
// Function to calculate the pascal triangle
void pascalTriangle()
{
    pascal[0][0] = 1;
    pascal[1][0] = 1;
    pascal[1][1] = 1;
 
    // Loop to calculate values of
    // pascal triangle
    for (int i = 2; i < 31; i++) {
        pascal[i][0] = 1;
        for (int j = 1; j < i; j++)
            pascal[i][j]
                = pascal[i - 1][j]
                  + pascal[i - 1][j - 1];
        pascal[i][i] = 1;
    }
}
 
// Function to calculate the number of ways
long long int countWays(int n, int p, int q)
{
 
    // Variable to store the answer
    long long int sum = 0;
 
    // Loop to calculate the number of ways
    for (long long int i = 4; i <= p; i++) {
        if (n - i >= 1 && n - i <= q)
            sum += pascal[p][i]
                   * pascal[q][n - i];
    }
    return sum;
}
 
// Driver code
int main()
{
    pascalTriangle();
 
    int P = 5, Q = 2, N = 5;
 
    // Calculate possible ways for given
    // N, P, and Q
    cout << countWays(N, P, Q) << endl;
    return 0;
}


Java




import java.util.*;
public class GFG
{
     
static long [][]pascal = new long[31][31];
 
// Function to calculate the pascal triangle
static void pascalTriangle()
{
    pascal[0][0] = 1;
    pascal[1][0] = 1;
    pascal[1][1] = 1;
 
    // Loop to calculate values of
    // pascal triangle
    for (int i = 2; i < 31; i++) {
        pascal[i][0] = (int)1;
        for (int j = 1; j < i; j++)
            pascal[i][j]
                = pascal[i - 1][j]
                  + pascal[i - 1][j - 1];
        pascal[i][i] = 1;
    }
}
 
// Function to calculate the number of ways
static long countWays(int n, int p, int q)
{
 
    // Variable to store the answer
    long sum = 0;
 
    // Loop to calculate the number of ways
    for (int i = 4; i <= p; i++) {
        if (n - i >= 1 && n - i <= q) {
            sum += (int)pascal[p][i]
                   * (int)pascal[q][n - i];
        }
    }
    return sum;
}
 
// Driver code
public static void main(String args[])
{
    pascalTriangle();
 
    int P = 5, Q = 2, N = 5;
 
    // Calculate possible ways for given
    // N, P, and Q
    System.out.print(countWays(N, P, Q));
 
}
}
// This code is contributed by Samim Hossain Mondal.


Python3




# Python3 program for the above approach
import numpy as np
 
pascal = np.zeros((31,31));
 
# Function to calculate the pascal triangle
def pascalTriangle() :
     
    pascal[0][0] = 1;
    pascal[1][0] = 1;
    pascal[1][1] = 1;
 
    # Loop to calculate values of
    # pascal triangle
    for i in range(2, 31) :
         
        pascal[i][0] = 1;
        for j in range(1, i) :
            pascal[i][j] = pascal[i - 1][j] + pascal[i - 1][j - 1];
         
        pascal[i][i] = 1;
   
 
# Function to calculate the number of ways
def countWays(n, p, q) :
 
    # Variable to store the answer
    sum = 0;
 
    # Loop to calculate the number of ways
    for i in range(4, p + 1) :
         
        if (n - i >= 1 and n - i <= q) :
             
            sum += pascal[p][i] * pascal[q][n - i];
 
    return int(sum);
 
# Driver code
if __name__ ==  "__main__" :
 
    pascalTriangle();
 
    P = 5; Q = 2; N = 5;
 
    # Calculate possible ways for given
    # N, P, and Q
    print(countWays(N, P, Q));
 
    # This code is contributed by AnkThon


C#




using System;
class GFG
{
     
static long [,]pascal = new long[31, 31];
 
// Function to calculate the pascal triangle
static void pascalTriangle()
{
    pascal[0, 0] = 1;
    pascal[1, 0] = 1;
    pascal[1, 1] = 1;
 
    // Loop to calculate values of
    // pascal triangle
    for (int i = 2; i < 31; i++) {
        pascal[i, 0] = (int)1;
        for (int j = 1; j < i; j++)
            pascal[i, j]
                = pascal[i - 1, j]
                  + pascal[i - 1, j - 1];
        pascal[i, i] = 1;
    }
}
 
// Function to calculate the number of ways
static long countWays(int n, int p, int q)
{
 
    // Variable to store the answer
    long sum = 0;
 
    // Loop to calculate the number of ways
    for (int i = 4; i <= p; i++) {
        if (n - i >= 1 && n - i <= q) {
            sum += (int)pascal[p, i]
                   * (int)pascal[q, n - i];
        }
    }
    return sum;
}
 
// Driver code
public static void Main()
{
    pascalTriangle();
 
    int P = 5, Q = 2, N = 5;
 
    // Calculate possible ways for given
    // N, P, and Q
    Console.Write(countWays(N, P, Q));
 
}
}
// This code is contributed by Samim Hossain Mondal.


Javascript




<script>
 
    let pascal = new Array(31).fill(0).map(() => new Array(31).fill(0));
 
    // Function to calculate the pascal triangle
    const pascalTriangle = () => {
        pascal[0][0] = 1;
        pascal[1][0] = 1;
        pascal[1][1] = 1;
 
        // Loop to calculate values of
        // pascal triangle
        for (let i = 2; i < 31; i++) {
            pascal[i][0] = 1;
            for (let j = 1; j < i; j++)
                pascal[i][j]
                    = pascal[i - 1][j]
                    + pascal[i - 1][j - 1];
            pascal[i][i] = 1;
        }
    }
 
    // Function to calculate the number of ways
    const countWays = (n, p, q) => {
 
        // Variable to store the answer
        let sum = 0;
 
        // Loop to calculate the number of ways
        for (let i = 4; i <= p; i++) {
            if (n - i >= 1 && n - i <= q)
                sum += pascal[p][i]
                    * pascal[q][n - i];
        }
        return sum;
    }
 
    // Driver code
    pascalTriangle();
 
    let P = 5, Q = 2, N = 5;
 
    // Calculate possible ways for given
    // N, P, and Q
    document.write(countWays(N, P, Q));
 
// This code is contributed by rakeshsahni
 
</script>


 
 

Output

10

 

Time Complexity: O(N)
Auxiliary Space: O(N2)

 

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Commit to GfG’s Three-90 Challenge! Purchase a course, complete 90% in 90 days, and save 90% cost click here to explore.

Last Updated :
06 Dec, 2021
Like Article
Save Article


Previous

<!–

8 Min Read | Java

–>


Next


<!–

8 Min Read | Java

–>

Share your thoughts in the comments

RELATED ARTICLES

Most Popular

Recent Comments