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 1st and 2nd women.
Way 2: Choose the only man and 2nd and 3rd women.
Way 3: Choose the only man and 1st and 3rd 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 MCX and the total number of ways of choosing Y women from W women is WCY. Hence, the total number of combined ways will be MCX * WCY.
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 effectivelyint 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 waysint 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 effectivelydef 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 waysdef totalWays(X, Y, M, W): return (ncr(M, X) * ncr(W, Y))X = 4Y = 3M = 6W = 5print(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 effectivelyfunction 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 waysfunction 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
150
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 numberint factorial(int n) { if (n == 0) { return 1; } else { return n * factorial(n - 1); }}// Function to return the count of required waysint 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 numberdef factorial(n): if n == 0: return 1 else: return n * factorial(n - 1)# Function to return the count of required waysdef 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 codeif __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 numberfunction factorial(n) { if (n === 0) { return 1; } else { return n * factorial(n - 1); }}// Function to return the count of required waysfunction 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
150
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
