Given non-negative integers X, Y, and Z for each M query. Given X amount of character ‘A’, Y amount of character ‘B’, and Z amount of character ‘C’. The task is to print for each query, the number of ways modulo 109 + 7 of arranging these characters in a row so that at least one character is separated from a character of the same type.
AABBCCC, BBBBBCCCCAAA, and ABBBCCCCC are some invalid answers since no characters are separated from characters of the same type.
Examples:
Input: Q[][3] = {{1, 1, 1}, {1, 2, 1}, {2, 2, 1}}, N = 3
Output: 0 6 24
Explanation: For query 1: X = 1, Y = 1, and Z = 1, with these characters it is not possible to arrange them in such a way that at least one character is separated from characters of the same type.
For query 2: X = 1, Y = 2, and Z = 1, with these there are 6 possible arrangements ABCB, BACB, BABC, CBAB, BCAB, and BCBA.
For query 3: X = 2, Y = 2 and Z = 1 with these there are 24 possible arrangements.Input: Q1[][3] = {{2, 3, 5}, {5, 6, 7}, {8, 9, 10}}, N = 3
Output: 2514 14702682 86086909
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.number
Time Complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Combinatorics can be used along with binary exponentiation and modulo multiplicative inverse to solve this problem
- Precomputing factorials for each query.
- Total permutations = 0 characters separated + 1 character separated + 2 characters separated + 3 characters separated + …………………. = (X + Y + Z)! / (X! * Y! * Z!).
- It will suffice to exclude 0 characters separated permutations from Total permutations in order to find out permutations with at least 1 character separated.
- Total permutations with at least 1 character separated = Total permutations with no restriction – permutations with zero 0 characters separated.
- if we consider all same characters as one object there are 3! ways of permutating them.
- Total permutations with at least 1 character separated = (X + Y + Z)! / (X! * Y! * Z!) – 3! = (X + Y + Z)! / (X! * Y! * Z!) – 6
- For calculation instead of division by X! , Y! and Z!. Its better to multiplying answer by modulo multiplicative inverse of X!, Y! and Z! along with stepwise multiplication to avoid integer overflow.
Follow the steps below to solve the problem:
- Making factorial array fact[] for precomputation and filling the array with factorials of numbers from 1 to 100000.
- Traversing for each query 1 to M and printing the answer by the above formula.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;#define int long longconst int MOD = 1e9 + 7;// To compute x raised to power y// under modulo Mint power(int x, unsigned int y, unsigned int M);// Function to find modular inverse of a// under modulo M// Assumption: M is primeint modInverse(int A, int M){ // If a and m are relatively prime, // then modulo inverse is // a^(m-2) mode m return power(A, M - 2, M);}// To compute x^y under modulo mint power(int x, unsigned int y, unsigned int M){ if (y == 0) return 1; int p = power(x, y / 2, M) % M; p = (p * p) % M; return (y % 2 == 0) ? p : (x * p) % M;}// Function to print Count ways given// characters arranged in row so that// at least on character is separated// from character of same type for each M// queries.void findWays(int Q[][3], int M){ // Precomputing factorial array int fact[100001]; // Factorial of 1 is 1 fact[1] = 1; // Finding factorial of all 1e5 numbers for (int i = 2; i <= 1e5; i++) { fact[i] = (fact[i - 1] * i) % MOD; } // Traversing for each query for (int i = 0; i < M; i++) { // X, Y and Z for i'th query int X = Q[i][0], Y = Q[i][1], Z = Q[i][2]; // Total permutation = // (X + Y + Z)! / X! int ans = (fact[X + Y + Z] * modInverse(fact[X], MOD)) % MOD; // Total permutation = // (X + Y + Z)! / (X! * Y!) ans = (ans * modInverse(fact[Y], MOD)) % MOD; // Total permutation = // (X + Y + Z)! (X! * Y! * Z!) ans = (ans * modInverse(fact[Z], MOD)) % MOD; // Printing answer cout << ans - 6 << " "; } cout << endl;}// Driver Codeint32_t main(){ // Test Case 1 int Q[][3] = { { 1, 1, 1 }, { 1, 2, 1 }, { 2, 2, 1 } }, N = 3; // Function Call findWays(Q, N); // Test Case 2 int Q1[][3] = { { 2, 3, 5 }, { 5, 6, 7 }, { 8, 9, 10 } }, N1 = 3; // Function Call findWays(Q1, N1); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { final static long MOD = (long)1e9 + 7; // To compute x raised to power y // under modulo M static long power(long x, long y, long M) { if (y == 0) return 1; long p = power(x, y / 2, M) % M; p = (p * p) % M; return (y % 2 == 0) ? p : (x * p) % M; } // Function to find modular inverse of a // under modulo M // Assumption: M is prime static long modInverse(long A, long M) { // If a and m are relatively prime, // then modulo inverse is // a^(m-2) mode m return power(A, M - 2, M); } // Function to print Count ways given // characters arranged in row so that // at least on character is separated // from character of same type for each M // queries. static void findWays(int[][] Q, int M) { // Precomputing factorial array long[] fact = new long[100001]; // Factorial of 1 is 1 fact[1] = 1; // Finding factorial of all 1e5 numbers for (int i = 2; i <= 1e5; i++) { fact[i] = (fact[i - 1] * i) % MOD; } // Traversing for each query for (int i = 0; i < M; i++) { // X, Y and Z for i'th query int X = Q[i][0], Y = Q[i][1], Z = Q[i][2]; // Total permutation = // (X + Y + Z)! / X! long ans = (fact[X + Y + Z] * modInverse(fact[X], MOD)) % MOD; // Total permutation = // (X + Y + Z)! / (X! * Y!) ans = (ans * modInverse(fact[Y], MOD)) % MOD; // Total permutation = // (X + Y + Z)! (X! * Y! * Z!) ans = (ans * modInverse(fact[Z], MOD)) % MOD; // Printing answer System.out.print(ans - 6 + " "); } System.out.println(); } public static void main(String[] args) { // Test Case 1 int[][] Q = { { 1, 1, 1 }, { 1, 2, 1 }, { 2, 2, 1 } }; int N = 3; // Function Call findWays(Q, N); // Test Case 2 int[][] Q1 = { { 2, 3, 5 }, { 5, 6, 7 }, { 8, 9, 10 } }; int N1 = 3; // Function Call findWays(Q1, N1); }}// This code is contributed by lokesh. |
Python3
# Python3 code to implement the approachMOD = int(1e9 + 7)# To compute x raised to power y# under modulo Mdef power(x: int, y: int, M: int) -> int: if y == 0: return 1 p = power(x, y // 2, M) % M p = (p * p) % M return (p if y % 2 == 0 else (x * p) % M)# Function to find modular inverse of a# under modulo M# Assumption: M is primedef modInverse(A: int, M: int) -> int: # If a and m are relatively prime, # then modulo inverse is # a^(m-2) mode m return power(A, M - 2, M)# Function to print Count waysdef findWays(Q: list, M: int): # Precomputing factorial array fact = [0 for _ in range(100001)] # Factorial of 1 is 1 fact[1] = 1 # Finding factorial of all 1e5 numbers for i in range(2, int(1e5) + 1): fact[i] = (fact[i - 1] * i) % MOD # Traversing for each query for i in range(M): # X, Y and Z for i'th query X, Y, Z = Q[i] # Total permutation = # (X + Y + Z)! / X! ans = (fact[X + Y + Z] * modInverse(fact[X], MOD)) % MOD # Total permutation = # (X + Y + Z)! / (X! * Y!) ans = (ans * modInverse(fact[Y], MOD)) % MOD # Total permutation = # (X + Y + Z)! (X! * Y! * Z!) ans = (ans * modInverse(fact[Z], MOD)) % MOD # Printing answer print(ans - 6, end=' ') print()# Driver Codeif __name__ == "__main__": # Test Case 1 Q = [[1, 1, 1], [1, 2, 1], [2, 2, 1]] N = 3 # Function Call findWays(Q, N) # Test Case 2 Q1 = [[2, 3, 5], [5, 6, 7], [8, 9, 10]] N1 = 3 # Function Call findWays(Q1, N1)# This code is contributed by lokeshpotta20. |
C#
// C# code to implement the approachusing System;using System.Linq;using System.Collections.Generic;public class GFG { public const long MOD = (long)1e9 + 7; // To compute x raised to power y // under modulo M static long power(long x, long y, long M) { if (y == 0) return 1; long p = power(x, y / 2, M) % M; p = (p * p) % M; return (y % 2 == 0) ? p : (x * p) % M; } // Function to find modular inverse of a // under modulo M // Assumption: M is prime static long modInverse(long A, long M) { // If a and m are relatively prime, // then modulo inverse is // a^(m-2) mode m return power(A, M - 2, M); } // Function to print Count ways given // characters arranged in row so that // at least on character is separated // from character of same type for each M // queries. static void findWays(int[, ] Q, int M) { // Precomputing factorial array long[] fact = new long[100001]; // Factorial of 1 is 1 fact[1] = 1; // Finding factorial of all 1e5 numbers for (int i = 2; i <= 1e5; i++) { fact[i] = (fact[i - 1] * i) % MOD; } // Traversing for each query for (int i = 0; i < M; i++) { // X, Y and Z for i'th query int X = Q[i, 0], Y = Q[i, 1], Z = Q[i, 2]; // Total permutation = // (X + Y + Z)! / X! long ans = (fact[X + Y + Z] * modInverse(fact[X], MOD)) % MOD; // Total permutation = // (X + Y + Z)! / (X! * Y!) ans = (ans * modInverse(fact[Y], MOD)) % MOD; // Total permutation = // (X + Y + Z)! (X! * Y! * Z!) ans = (ans * modInverse(fact[Z], MOD)) % MOD; // Printing answer Console.Write(ans - 6 + " "); } Console.WriteLine(); } static public void Main() { // Code // Test Case 1 int[, ] Q = { { 1, 1, 1 }, { 1, 2, 1 }, { 2, 2, 1 } }; int N = 3; // Function Call findWays(Q, N); // Test Case 2 int[, ] Q1 = { { 2, 3, 5 }, { 5, 6, 7 }, { 8, 9, 10 } }; int N1 = 3; // Function Call findWays(Q1, N1); }}// This code is contributed by lokeshmvs21. |
Javascript
// Javascript code to implement the approachconst MOD = BigInt(1e9 + 7);// To compute x raised to power y// under modulo Mfunction power(x, y, M) { if (y == 0n) { return 1n; } let p = power(x, y / 2n, M) % M; p = (p * p) % M; return (y % 2n == 0n ? p : (x * p) % M);}// Function to find modular inverse of a// under modulo M// Assumption: M is primefunction modInverse(A, M) { // If a and m are relatively prime, // then modulo inverse is // a^(m-2) mode m return power(A, M - 2n, M);}// Function to print Count waysfunction findWays(Q, M) { // Precomputing factorial array const fact = new Array(100001).fill(0n); // Factorial of 1 is 1 fact[1] = 1n; // Finding factorial of all 1e5 numbers for (let i = 2; i <= 1e5; i++) { fact[i] = (fact[i - 1] * BigInt(i)) % MOD; } // Traversing for each query for (let i = 0; i < M; i++) { // X, Y and Z for i'th query const [X, Y, Z] = Q[i]; // Total permutation = // (X + Y + Z)! / X! let ans = (fact[X + Y + Z] * modInverse(fact[X], MOD)) % MOD; // Total permutation = // (X + Y + Z)! / (X! * Y!) ans = (ans * modInverse(fact[Y], MOD)) % MOD; // Total permutation = // (X + Y + Z)! (X! * Y! * Z!) ans = (ans * modInverse(fact[Z], MOD)) % MOD; // Printing answer process.stdout.write((ans - 6n) + ' '); } process.stdout.write('\n');}// Test Case 1const Q = [[1, 1, 1], [1, 2, 1], [2, 2, 1]];const N = 3;// Function CallfindWays(Q, N);// Test Case 2const Q1 = [[2, 3, 5], [5, 6, 7], [8, 9, 10]];const N1 = 3;// Function CallfindWays(Q1, N1); |
Output
0 6 24 2514 14702682 86086909
Time Complexity: O(M), Where M is the number of queries.
Auxiliary Space: O(M)
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!
