Given integers X and Y representing X girls and Y boys, the task is to count the number of ways arranging X girls and Y boys such that girls always stay together and two boys from Y refuse to stay consecutive. Print the answer modulo 109 + 7.
Examples:
Input: X = 2, Y = 2
Output: 4
Explanation: Let’s say girls are G1 and G2 and Boys are B1 and B2, considering B1 and B2 refuse to stay consecutive some valid permutations are B1G1G2B2, B2G1G2B1, B1G2G1B2 and B2G2G1B1.Input: X = 3, Y = 7
Output: 181440
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(N!), where N is X + Y
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
The problem can be solved with combinatorics:
- Total valid arrangements = Total arrangements – Total invalid arrangements
- Total valid arrangements with all girls together and 2 boys from Y are not consecutive = Total valid arrangements with all girls together – Total valid arrangements with all girls together and two boys from Y always together.
- Valid arrangements = (Y + 1)! X! – Y! * 2! * X!
Calculating answer with stepwise Modulo to avoid integer overflow.
Follow the steps below to solve the problem:
- Initializing fact[] array and Precomputing all factorials from 1 to 100000.
- Initializing ANS variable.
- Calculating the answer by using the above formula.
- Print the answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;const int MOD = 1e9 + 7;// Function to Count number of ways// following people can be arrangedint countWays(int X, int Y){ // Precomputation array storing // factorials MOD 1e9 + 7 int fact[100001]; // Initialize the first element fact[1] = 1; // Filling factorial table for (int i = 2; i <= 100000; i++) { fact[i] = (fact[i - 1] * i) % MOD; } // Storing Total number of arrangements // with all girls together int ans = (fact[Y + 1] * fact[X]) % MOD; // Subtracting invalid 2 boys always // together ans = ans - (fact[Y] * fact[X] * fact[2]) % MOD; // Adding MOD to avoid ans being negative ans = (ans + MOD) % MOD; // returning the answer return ans;}// Driver Codeint main(){ // Input 1 int X = 2, Y = 2; // Function Call cout << countWays(X, Y) << endl; // Input 2 int X1 = 3, Y1 = 7; // Function Call cout << countWays(X1, Y1) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { static int MOD = (int)1e9 + 7; // Function to Count number of ways // following people can be arranged static int countWays(int X, int Y) { // Precomputation array storing // factorials MOD 1e9 + 7 int[] fact = new int[100001]; // Initialize the first element fact[1] = 1; // Filling factorial table for (int i = 2; i <= 100000; i++) { fact[i] = (fact[i - 1] * i) % MOD; } // Storing Total number of arrangements // with all girls together int ans = (fact[Y + 1] * fact[X]) % MOD; // Subtracting invalid 2 boys always // together ans = ans - (fact[Y] * fact[X] * fact[2]) % MOD; // Adding MOD to avoid ans being negative ans = (ans + MOD) % MOD; // returning the answer return ans; } public static void main(String[] args) { // Input 1 int X = 2, Y = 2; // Function Call System.out.println(countWays(X, Y)); // Input 2 int X1 = 3, Y1 = 7; // Function Call System.out.println(countWays(X1, Y1)); }}// This code is contributed by lokesh. |
Python3
# Set the constant MOD to 1e9 + 7MOD = 1e9 + 7def count_ways(X, Y): # Initialize a list "fact" to store factorials # Set the first element to 1 fact = [1] * 100001 # Fill the rest of the "fact" list with the factorials # of the corresponding indices, modulo MOD for i in range(2, 100001): fact[i] = (fact[i - 1] * i) % MOD # Initialize "ans" to the number of arrangements # with all the girls together ans = (fact[Y + 1] * fact[X]) % MOD # Subtract the number of invalid arrangements where # 2 boys are always together ans = ans - (fact[Y] * fact[X] * fact[2]) % MOD # Add MOD to ensure "ans" is non-negative ans = (ans + MOD) % MOD # Return the final result return ans# Driver codeX=2Y=2print(int(count_ways(X,Y)))X1=3Y1=7print(int(count_ways(X1,Y1)))#This code is contributed by Potta Lokesh |
C#
// C# code to implement the approachusing System;namespace ConsoleApp{ class Program { // Function to Count number of ways // following people can be arranged static int CountWays(int X, int Y) { const int MOD = 1000000000 + 7; // Precomputation array storing // factorials MOD 1e9 + 7 int[] fact = new int[100001]; // Initialize the first element fact[1] = 1; // Filling factorial table for (int i = 2; i <= 100000; i++) { fact[i] = (fact[i - 1] * i) % MOD; } // Storing Total number of arrangements // with all girls together int ans = (fact[Y + 1] * fact[X]) % MOD; // Subtracting invalid 2 boys always // together ans = ans - (fact[Y] * fact[X] * fact[2]) % MOD; // Adding MOD to avoid ans being negative ans = (ans + MOD) % MOD; return ans; } static void Main(string[] args) { int X = 2, Y = 2; Console.WriteLine(CountWays(X, Y)); int X1 = 3, Y1 = 7; Console.WriteLine(CountWays(X1, Y1)); } }} |
Javascript
const MOD = 1e9 + 7;// Function to Count number of ways// following people can be arrangedfunction countWays(X, Y) { // Precomputation array storing // factorials MOD 1e9 + 7 let fact = Array(100001).fill(0); // Initialize the first element fact[1] = 1; // Filling factorial table for (let i = 2; i <= 100000; i++) { fact[i] = (fact[i - 1] * i) % MOD; } // Storing Total number of arrangements // with all girls together let ans = (fact[Y + 1] * fact[X]) % MOD; // Subtracting invalid 2 boys always // together ans = ans - (fact[Y] * fact[X] * fact[2]) % MOD; // Adding MOD to avoid ans being negative ans = (ans + MOD) % MOD; // returning the answer return ans;}// Driver Codeconsole.log(countWays(2, 2));console.log(countWays(3, 7));//code by ksam24000 |
Output
4 181440
Time Complexity: O(N), where N is X + Y.
Auxiliary Space: O(N)
Related Articles:
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!
Share your thoughts in the comments
