Total ways of choosing X men and Y women from a total of M men and W women

0 0 7 minutes read

Given four integers X, Y, M, and W. The task is to find the number of ways to choose X men and Y women from total M men and W women.

Examples:

Input: X = 1, Y = 2, M = 1, W = 3
Output: 3
Way 1: Choose the only man and 1^st and 2^nd women.
Way 2: Choose the only man and 2^nd and 3^rd women.
Way 3: Choose the only man and 1^st and 3^rd women.

Input: X = 4, Y = 3, M = 6, W = 5
Output: 150

Approach: The total number of ways of choosing X men from a total of M men is ^MC_X and the total number of ways of choosing Y women from W women is ^WC_Y. Hence, the total number of combined ways will be ^MC_X * ^WC_Y.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// value of ncr effectively
int ncr(int n, int r)
{
 
    // Initialize the answer
    int ans = 1;
 
    for (int i = 1; i <= r; i += 1) {
 
        // Divide simultaneously by
        // i to avoid overflow
        ans *= (n - r + i);
        ans /= i;
    }
    return ans;
}
 
// Function to return the count of required ways
int totalWays(int X, int Y, int M, int W)
{
    return (ncr(M, X) * ncr(W, Y));
}
 
int main()
{
    int X = 4, Y = 3, M = 6, W = 5;
 
    cout << totalWays(X, Y, M, W);
 
    return 0;
}

Java

// JAVA implementation of the approach 
import java.io.*;
 
class GFG 
{
         
    // Function to return the 
    // value of ncr effectively 
    static int ncr(int n, int r) 
    { 
     
        // Initialize the answer 
        int ans = 1; 
     
        for (int i = 1; i <= r; i += 1) 
        { 
     
            // Divide simultaneously by 
            // i to avoid overflow 
            ans *= (n - r + i); 
            ans /= i; 
        } 
        return ans; 
    } 
     
    // Function to return the count of required ways 
    static int totalWays(int X, int Y, int M, int W) 
    { 
        return (ncr(M, X) * ncr(W, Y)); 
    } 
     
    // Driver code
    public static void main (String[] args) 
    {
        int X = 4, Y = 3, M = 6, W = 5; 
     
        System.out.println(totalWays(X, Y, M, W)); 
    }
}
 
// This code is contributed by ajit_23

Python3

# Python3 implementation of the approach
 
# Function to return the
# value of ncr effectively
def ncr(n, r):
    # Initialize the answer
    ans = 1
 
    for i in range(1,r+1):
 
        # Divide simultaneously by
        # i to avoid overflow
        ans *= (n - r + i)
        ans //= i
    return ans
 
# Function to return the count of required ways
def totalWays(X, Y, M, W):
 
    return (ncr(M, X) * ncr(W, Y))
 
X = 4
Y = 3
M = 6
W = 5
 
print(totalWays(X, Y, M, W))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach 
using System;
 
class GFG
{
     
    // Function to return the 
    // value of ncr effectively 
    static int ncr(int n, int r) 
    { 
     
        // Initialize the answer 
        int ans = 1; 
     
        for (int i = 1; i <= r; i += 1) 
        { 
     
            // Divide simultaneously by 
            // i to avoid overflow 
            ans *= (n - r + i); 
            ans /= i; 
        } 
        return ans; 
    } 
     
    // Function to return the count of required ways 
    static int totalWays(int X, int Y, int M, int W) 
    { 
        return (ncr(M, X) * ncr(W, Y)); 
    } 
     
    // Driver code
    static public void Main ()
    {
        int X = 4, Y = 3, M = 6, W = 5; 
     
        Console.WriteLine(totalWays(X, Y, M, W)); 
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
// Javascript implementation of the approach
 
// Function to return the
// value of ncr effectively
function ncr(n, r)
{
 
    // Initialize the answer
    let ans = 1;
 
    for (let i = 1; i <= r; i += 1) {
 
        // Divide simultaneously by
        // i to avoid overflow
        ans *= (n - r + i);
        ans = parseInt(ans / i);
    }
    return ans;
}
 
// Function to return the count of required ways
function totalWays(X, Y, M, W)
{
    return (ncr(M, X) * ncr(W, Y));
}
 
// Driver Code
    let X = 4, Y = 3, M = 6, W = 5;
 
    document.write(totalWays(X, Y, M, W));
 
// This code is contributed by rishavmahato348.
</script>

Output

Time Complexity: O(n)

Auxiliary Space: O(1)

Approach:

Here, Another approach to solve this problem is to use the concept of permutations and combinations. We can choose X men from M men in MCX ways, and Y women from W women in WCY ways. To get the total number of ways of choosing X men and Y women, we need to multiply these two values.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the factorial of a number
int factorial(int n) 
{
    if (n == 0) 
    {
        return 1;
    } 
    else
    {
        return n * factorial(n - 1);
    }
}
 
// Function to return the count of required ways
int totalWays(int X, int Y, int M, int W) 
{
    int waysToChooseMen = 1;
    for (int i = M; i >= M - X + 1; i--)
    {
        waysToChooseMen *= i;
    }
    waysToChooseMen /= factorial(X);
 
    int waysToChooseWomen = 1;
    for (int i = W; i >= W - Y + 1; i--)
    {
        waysToChooseWomen *= i;
    }
    waysToChooseWomen /= factorial(Y);
 
    return waysToChooseMen * waysToChooseWomen;
}
 
 
int main () 
{
    int X = 4, Y = 3, M = 6, W = 5;
    cout << totalWays(X, Y, M, W);
    return 0;
}

Java

import java.util.*;
 
public class Main {
    // Function to calculate the factorial of a number
    static int factorial(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
 
    // Function to return the count of required ways
    static int totalWays(int X, int Y, int M, int W) {
        int waysToChooseMen = 1;
        for (int i = M; i >= M - X + 1; i--) {
            waysToChooseMen *= i;
        }
        waysToChooseMen /= factorial(X);
 
        int waysToChooseWomen = 1;
        for (int i = W; i >= W - Y + 1; i--) {
            waysToChooseWomen *= i;
        }
        waysToChooseWomen /= factorial(Y);
 
        return waysToChooseMen * waysToChooseWomen;
    }
 
    public static void main(String[] args) {
        int X = 4, Y = 3, M = 6, W = 5;
        System.out.println(totalWays(X, Y, M, W));
    }
}

Python3

# Function to calculate the factorial of a number
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)
 
# Function to return the count of required ways
def totalWays(X, Y, M, W):
    # Calculate the ways to choose X men from M men
    waysToChooseMen = 1
    for i in range(M, M - X, -1):
        waysToChooseMen *= i
    waysToChooseMen //= factorial(X)
 
    # Calculate the ways to choose Y women from W women
    waysToChooseWomen = 1
    for i in range(W, W - Y, -1):
        waysToChooseWomen *= i
    waysToChooseWomen //= factorial(Y)
 
    # Return the total ways by multiplying the ways to choose men and women
    return waysToChooseMen * waysToChooseWomen
 
# Main code
if __name__ == "__main__":
    X = 4
    Y = 3
    M = 6
    W = 5
    print(totalWays(X, Y, M, W))

C#

using System;
 
public class GFG
{
    // Function to calculate the factorial of a number
    public static int Factorial(int n)
    {
        if (n == 0)
        {
            return 1;
        }
        else
        {
            // Recursive call to calculate factorial
            return n * Factorial(n - 1);
        }
    }
 
    // Function to return the count of required ways
    public static int TotalWays(int X, int Y, int M, int W)
    {
        // Calculate the ways to choose X men from M
        int waysToChooseMen = 1;
        for (int i = M; i >= M - X + 1; i--)
        {
            waysToChooseMen *= i;
        }
        waysToChooseMen /= Factorial(X);
 
        // Calculate the ways to choose Y women from W
        int waysToChooseWomen = 1;
        for (int i = W; i >= W - Y + 1; i--)
        {
            waysToChooseWomen *= i;
        }
        waysToChooseWomen /= Factorial(Y);
 
        // Calculate the total ways by multiplying the ways to choose men and women
        return waysToChooseMen * waysToChooseWomen;
    }
 
    public static void Main(string[] args)
    {
        int X = 4, Y = 3, M = 6, W = 5;
         
        // Calculate and print the total ways to choose X men from M and Y women from W
        Console.WriteLine("Total ways: " + TotalWays(X, Y, M, W));
    }
}

Javascript

// Function to calculate the factorial of a number
function factorial(n) {
    if (n === 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}
 
// Function to return the count of required ways
function totalWays(X, Y, M, W) {
    let waysToChooseMen = 1;
    for (let i = M; i >= M - X + 1; i--) {
        waysToChooseMen *= i;
    }
    waysToChooseMen /= factorial(X);
 
    let waysToChooseWomen = 1;
    for (let i = W; i >= W - Y + 1; i--) {
        waysToChooseWomen *= i;
    }
    waysToChooseWomen /= factorial(Y);
 
    return waysToChooseMen * waysToChooseWomen;
}
 
function main() {
    const X = 4, Y = 3, M = 6, W = 5;
    console.log(totalWays(X, Y, M, W));
}
 
main();

Output

Time Complexity:- O(X + Y)
Auxiliary Space:- O(1)

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 zambiatek!