|
Rahul entered the lift on the ground floor of his building which consists of Z floors including the ground floor. The lift already had N people in it. It is known that they will leave the lift in groups. Let us say that there are M groups. Rahul is curious to find the number of ways in which these M groups can leave the lift. It is assumed that each group is unique and no one leaves the lift on the ground floor.
Example:
Input: Z = 3, N = 10, M = 2
Output: 6
Explanation: Let the groups are A and B.
1. Both A and B gets down on first floor A going first followed by B
2. Both A and B gets down on first floor B going first followed by A
3. Both A and B gets down on second floor A going first followed by B
4. Both A and B gets down on second floor B going first followed by A
5. A gets down of first floor and B gets down on second.
6. B gets down of first floor and A gets down on second.
Input: Z = 4, N = 6, M = 2
Output: 12
Approach:
The idea is to uses a combination formula: C(n, r) = n! / (r! * (n-r)!), where n! denotes the factorial of n. In this context, the number of ways a group of M people can choose Z floors (excluding the ground floor) is calculated as C(Z + M – 2, M), as there are Z + M – 2 choices (Z floors excluding the ground floor plus M groups).
Let’s break down why there are C(Z + M – 2, M) choices:
Z Floors:
- The building has Z floors, including the ground floor.
- Since we don’t want anyone to leave the lift on the ground floor, we have Z – 1 choices for each person (from the first floor to the top floor).
M Groups:
- There are M groups of people leaving the lift.
- Each group is unique, implying that the composition of people in each group matters.
Choices for M Groups:
- The problem asks for the number of ways M groups can leave the lift.
- For each person in a group, there are Z – 1 choices (excluding the ground floor).
- Since there are M groups, and each group has multiple people, the total number of choices is (Z – 1) * (Z – 1) * … * (Z – 1) (M times).
Equivalent to Combination:
- The number of ways to make M choices from Z – 1 options (for each person) is a combination.
- Using the combination formula C(n, r) = n! / (r! * (n-r)!), where n is the total number of options, and r is the number of choices, the formula for this scenario is C(Z + M – 2, M).
- Here, n = Z + M – 2 (Z – 1) choices for each person in M groups) and r = M (number of groups).
Example:
- If there are 3 floors (Z = 3) and 2 groups (M = 2), then the choices would be C(3 + 2 – 2, 2) = C(3, 2) = 3, representing the combinations of choices for each group.
In summary, C(Z + M – 2, M) captures the number of ways M groups of people can leave the lift, considering the choices for each person in each group from the available floors.
Step-by-step approach:
- Our task is to find the number of ways M groups can leave the lift. Formula: (Z + M – 2)! / ((Z – 2)! * M!)
- Modular Arithmetic and Factorials:
- Create a modulus value (mod = 1e9 + 7) for modular arithmetic.
- Implement a power() function for efficient modular exponentiation.
- Implement a preCalculate() function to compute factorials and inverse factorials using modular arithmetic.
- Factorial and Inverse Factorial Calculation:
- Initialize arrays factorial and inverseFactorial to store factorials and inverse factorials.
- Calculate factorials up to 100000 using the formula: factorial[i] = (i * factorial[i-1]) % mod.
- Calculate inverse factorials in reverse order using the formula: inverseFactorial[i] = ((i+1) * inverseFactorial[i+1]) % mod.
- Number of Ways Calculation:
- In the noOfWays() function, call preCalculate() to set up factorials and inverse factorials.
- Use the combination formula to calculate the number of ways: (factorial[Z + M – 2] * inverseFactorial[Z – 2]) % mod.
- Return the result as an integer.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#define SIZE 100100
ll factorial[SIZE], inverseFactorial[SIZE];
ll mod = 1e9 + 7;
ll power(ll base, ll exponent)
{
ll result = 1;
while (exponent) {
if (exponent % 2)
result = (result * base) % mod;
base = (base * base) % mod;
exponent /= 2;
}
return result;
}
void preCalculate()
{
memset(factorial, 0, sizeof(factorial));
memset(inverseFactorial, 0, sizeof(inverseFactorial));
factorial[0] = 1;
for (int i = 1; i < 100001; ++i)
factorial[i] = (i * factorial[i - 1]) % mod;
inverseFactorial[100000]
= power(factorial[100000], mod - 2);
for (int i = 99999; i >= 0; i--)
inverseFactorial[i]
= ((i + 1) * inverseFactorial[i + 1]) % mod;
}
int noOfWays(int z, int n, int m)
{
preCalculate();
ll ans
= (factorial[z + m - 2] * inverseFactorial[z - 2])
% mod;
return (int)ans;
}
int main()
{
int z = 3, n = 10, m = 2;
int ans = noOfWays(z, n, m);
cout << ans << "\n";
return 0;
}
|
Java
import java.util.Arrays;
public class LiftGroups {
static final int SIZE = 100100;
static long[] factorial = new long[SIZE];
static long[] inverseFactorial = new long[SIZE];
static long mod = (long)1e9 + 7;
static long power(long base, long exponent)
{
long result = 1;
while (exponent > 0) {
if (exponent % 2 == 1)
result = (result * base) % mod;
base = (base * base) % mod;
exponent /= 2;
}
return result;
}
static void preCalculate()
{
Arrays.fill(factorial, 0);
Arrays.fill(inverseFactorial, 0);
factorial[0] = 1;
for (int i = 1; i < 100001; ++i)
factorial[i] = (i * factorial[i - 1]) % mod;
inverseFactorial[100000]
= power(factorial[100000], mod - 2);
for (int i = 99999; i >= 0; i--)
inverseFactorial[i]
= ((i + 1) * inverseFactorial[i + 1]) % mod;
}
static int noOfWays(int z, int n, int m)
{
preCalculate();
long ans = (factorial[z + m - 2]
* inverseFactorial[z - 2])
% mod;
return (int)ans;
}
public static void main(String[] args)
{
int z = 3, n = 10, m = 2;
int ans = noOfWays(z, n, m);
System.out.println(ans);
}
}
|
Python3
mod = 10**9 + 7
def power(base, exponent):
result = 1
while exponent:
if exponent % 2:
result = (result * base) % mod
base = (base * base) % mod
exponent //= 2
return result
def pre_calculate():
global factorial, inverse_factorial
factorial = [0] * 100100
inverse_factorial = [0] * 100100
factorial[0] = 1
for i in range(1, 100001):
factorial[i] = (i * factorial[i - 1]) % mod
inverse_factorial[100000] = power(factorial[100000], mod - 2)
for i in range(99999, 0, -1):
inverse_factorial[i] = ((i + 1) * inverse_factorial[i + 1]) % mod
def no_of_ways(z, n, m):
pre_calculate()
ans = (factorial[z + m - 2] * inverse_factorial[z - 2]) % mod
return ans
z = 3
n = 10
m = 2
ans = no_of_ways(z, n, m)
print(ans)
|
C#
using System;
public class Program
{
const int SIZE = 100100;
static long[] factorial = new long[SIZE];
static long[] inverseFactorial = new long[SIZE];
static long mod = 1000000007;
static long Power(long baseValue, long exponent)
{
long result = 1;
while (exponent > 0)
{
if (exponent % 2 == 1)
result = (result * baseValue) % mod;
baseValue = (baseValue * baseValue) % mod;
exponent /= 2;
}
return result;
}
static void PreCalculate()
{
Array.Fill(factorial, 0);
Array.Fill(inverseFactorial, 0);
factorial[0] = 1;
for (int i = 1; i < 100001; ++i)
factorial[i] = (i * factorial[i - 1]) % mod;
inverseFactorial[100000] = Power(factorial[100000], mod - 2);
for (int i = 99999; i >= 0; i--)
inverseFactorial[i] = ((i + 1) * inverseFactorial[i + 1]) % mod;
}
static int NoOfWays(int z, int n, int m)
{
PreCalculate();
long ans = (factorial[z + m - 2] * inverseFactorial[z - 2]) % mod;
return (int)ans;
}
public static void Main()
{
int z = 3, n = 10, m = 2;
int ans = NoOfWays(z, n, m);
Console.WriteLine(ans);
}
}
|
Javascript
const mod = 1e9 + 7;
function power(base, exponent) {
let result = 1;
while (exponent) {
if (exponent % 2)
result = (result * base) % mod;
base = (base * base) % mod;
exponent = Math.floor(exponent / 2);
}
return result;
}
function preCalculate() {
global.factorial = new Array(100100).fill(0);
global.inverseFactorial = new Array(100100).fill(0);
factorial[0] = 1;
for (let i = 1; i <= 100000; ++i) {
factorial[i] = (i * factorial[i - 1]) % mod;
inverseFactorial[i] = power(factorial[i], mod - 2);
}
}
function noOfWays(Z, N, M) {
preCalculate();
const numerator = factorial[Z + M - 2];
const denominator = (inverseFactorial[Z - 2] * inverseFactorial[M - 1]) % mod;
return (numerator * denominator) % mod;
}
const Z1 = 3, N1 = 10, M1 = 2;
const Z2 = 4, N2 = 6, M2 = 2;
const ans1 = noOfWays(Z1, N1, M1);
const ans2 = noOfWays(Z2, N2, M2);
console.log(ans1);
|
Time Complexity: O(N), where N is the size of the arrays (100100 in this case)
Auxiliary Space: O(N) due to the arrays factorial and inverseFactorial, each of size 100100.
|
