Given integers N, P, Q, X, and Y, the task is to find the number of ways to form a group of N people having at least X men and Y women from P men and Q women, where (X + Y ≤ N, X ≤ P and Y ≤ Q).
Examples:
Input: P = 4, Q = 2, N = 5, X = 3, Y = 1
Output: 6
Explanation: Suppose given pool is {m1, m2, m3, m4} and {w1, w2}. Then possible combinations are:
m1 m2 m3 m4 w1
m1 m2 m3 m4 w2
m1 m2 m3 w1 w2
m1 m2 m4 w1 w2
m1 m3 m4 w1 w2
m2 m3 m4 w1 w2Hence the count is 6.
Input: P = 5, Q = 2, N = 6, X = 4, Y = 1
Output: 7
Approach: This problem is based on combinatorics where we need to select at least X men out of P men available, and at least Y women out of Q women available, so that total people selected are N.Consider the example:
P = 4, Q = 2, N = 5, X = 3, Y = 1.
In this, the possible selections are:(4 men out of 4) * (1 women out of 2) + (3 men out of 4) * (2 woman out of 2)= 4C4 * 2C1 + 4C3 * 2C2
So for some general values of P, Q and N, the approach can be visualised as:
where
Follow the steps mentioned below to implement it:
- Start iterating a loop from i = X till i = P.
- Check if (N-i) satisfies the condition (N-i) ≥ Y and (N-i) ≤ Q. If the condition is satisfied then do as follows.
- At each iteration calculate the number of possible ways if we choose i men and (N-i) women.
- To get the number of possible ways for each iteration use the formula
- Add this value for each iteration with the total number of ways.
- Return the total value as your answer.
Below is the implementation of the approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to calculate factoriallong long int fact(int f){ f++; long long int ans = 1; // Loop to calculate factorial of f while (--f > 0) ans = ans * f; return ans;}// Function to calculate combination nCrlong long int ncr(int n, int r){ return (fact(n) / (fact(r) * fact(n - r)));}// Function to calculate the number of wayslong long int countWays(int n, int p, int q, int x, int y){ // Variable to store the answer long long int sum = 0; // Loop to calculate the number of ways for (long long int i = x; i <= p; i++) { if (n - i >= y && n - i <= q) sum += (ncr(p, i) * ncr(q, n - i)); } return sum;}// Driver codeint main(){ int P = 4, Q = 2, N = 5, X = 3, Y = 1; // Calculate possible ways for given // N, P, Q, X and Y cout << countWays(N, P, Q, X, Y) << endl; return 0;} |
Java
import java.util.*;public class GFG{ // Function to calculate factorial static long fact(long f) { f++; long ans = 1; // Loop to calculate factorial of f while (--f > 0) ans = ans * f; return ans; } // Function to calculate combination nCr static long ncr(long n, long r) { return (fact(n) / (fact(r) * fact(n - r))); } // Function to calculate the number of ways static long countWays(int n, int p, int q, int x, int y) { // Variable to store the answer long sum = 0; // Loop to calculate the number of ways for (long i = x; i <= p; i++) { if (n - i >= y && n - i <= q) sum += ((int)ncr(p, i) * (int)ncr(q, n - i)); } return sum; } // Driver code public static void main(String args[]) { int P = 4, Q = 2, N = 5, X = 3, Y = 1; // Calculate possible ways for given // N, P, Q, X and Y System.out.println(countWays(N, P, Q, X, Y)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Function to calculate factorialdef fact (f): ans = 1 # Loop to calculate factorial of f while (f): ans = ans * f f -= 1 return ans# Function to calculate combination nCrdef ncr (n, r): return (fact(n) // (fact(r) * fact(n - r)))# Function to calculate the number of waysdef countWays (n, p, q, x, y) : # Variable to store the answer sum = 0 # Loop to calculate the number of ways for i in range(x, p + 1): if (n - i >= y and n - i <= q): sum += (ncr(p, i) * ncr(q, n - i)) return sum# Driver codeP = 4Q = 2N = 5X = 3Y = 1# Calculate possible ways for given# N, P, Q, X and Yprint(countWays(N, P, Q, X, Y))# This code is contributed by gfgking |
C#
using System;class GFG{ // Function to calculate factorialstatic long fact(long f){ f++; long ans = 1; // Loop to calculate factorial of f while (--f > 0) ans = ans * f; return ans;}// Function to calculate combination nCrstatic long ncr(long n, long r){ return (fact(n) / (fact(r) * fact(n - r)));}// Function to calculate the number of waysstatic long countWays(int n, int p, int q, int x, int y){ // Variable to store the answer long sum = 0; // Loop to calculate the number of ways for (long i = x; i <= p; i++) { if (n - i >= y && n - i <= q) sum += ((int)ncr(p, i) * (int)ncr(q, n - i)); } return sum;}// Driver codepublic static void Main(){ int P = 4, Q = 2, N = 5, X = 3, Y = 1; // Calculate possible ways for given // N, P, Q, X and Y Console.Write(countWays(N, P, Q, X, Y));}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Function to calculate factorial const fact = (f) => { f++; let ans = 1; // Loop to calculate factorial of f while (--f > 0) ans = ans * f; return ans; } // Function to calculate combination nCr const ncr = (n, r) => { return (fact(n) / (fact(r) * fact(n - r))); } // Function to calculate the number of ways const countWays = (n, p, q, x, y) => { // Variable to store the answer let sum = 0; // Loop to calculate the number of ways for (let i = x; i <= p; i++) { if (n - i >= y && n - i <= q) sum += (ncr(p, i) * ncr(q, n - i)); } return sum; } // Driver code let P = 4, Q = 2, N = 5, X = 3, Y = 1; // Calculate possible ways for given // N, P, Q, X and Y document.write(countWays(N, P, Q, X, Y));// This code is contributed by rakeshsahni</script> |
Output
6
Time Complexity: O(N2)
Auxiliary Space: O(1)
Take a part in the ongoing discussion
