Count number of ways in which following people can be arranged

By Ann Roberts On Jan 6, 2023

Improve Article

Save Article

Like Article

Improve Article

Save Article

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 10⁹ + 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++

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int countWays(int X, int Y)

{

int fact[100001];

fact[1] = 1;

for (int i = 2; i <= 100000; i++) {

fact[i] = (fact[i - 1] * i) % MOD;

}

int ans = (fact[Y + 1] * fact[X]) % MOD;

ans = ans - (fact[Y] * fact[X] * fact[2]) % MOD;

ans = (ans + MOD) % MOD;

return ans;

}

int main()

{

int X = 2, Y = 2;

cout << countWays(X, Y) << endl;

int X1 = 3, Y1 = 7;

cout << countWays(X1, Y1) << endl;

return 0;

}

Time Complexity: O(N), where N is X + Y.
Auxiliary Space: O(N)

Related Articles:

Improve Article

Save Article

Like Article

Improve Article

Save Article

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++

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int countWays(int X, int Y)

{

int fact[100001];

fact[1] = 1;

for (int i = 2; i <= 100000; i++) {

fact[i] = (fact[i - 1] * i) % MOD;

}

int ans = (fact[Y + 1] * fact[X]) % MOD;

ans = ans - (fact[Y] * fact[X] * fact[2]) % MOD;

ans = (ans + MOD) % MOD;

return ans;

}

int main()

{

int X = 2, Y = 2;

cout << countWays(X, Y) << endl;

int X1 = 3, Y1 = 7;

cout << countWays(X1, Y1) << endl;

return 0;

}

Time Complexity: O(N), where N is X + Y.
Auxiliary Space: O(N)

Related Articles:

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.