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 w2Hence 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:
where
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 , i.e.
1
1 1
1 2 1
1 3 3 1
.
.
.
which is nothing but
.
.
.
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> |
10
Time Complexity: O(N)
Auxiliary Space: O(N2)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!