3317. Find the Number of Possible Ways for an Event LeetCode Solution
In this guide, you will get 3317. Find the Number of Possible Ways for an Event LeetCode Solution with the best time and space complexity. The solution to Find the Number of Possible Ways for an Event problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Find the Number of Possible Ways for an Event solution in C++
- Find the Number of Possible Ways for an Event solution in Java
- Find the Number of Possible Ways for an Event solution in Python
- Additional Resources
Problem Statement of Find the Number of Possible Ways for an Event
You are given three integers n, x, and y.
An event is being held for n performers. When a performer arrives, they are assigned to one of the x stages. All performers assigned to the same stage will perform together as a band, though some stages might remain empty.
After all performances are completed, the jury will award each band a score in the range [1, y].
Return the total number of possible ways the event can take place.
Since the answer may be very large, return it modulo 109 + 7.
Note that two events are considered to have been held differently if either of the following conditions is satisfied:
Any performer is assigned a different stage.
Any band is awarded a different score.
Example 1:
Input: n = 1, x = 2, y = 3
Output: 6
Explanation:
There are 2 ways to assign a stage to the performer.
The jury can award a score of either 1, 2, or 3 to the only band.
Example 2:
Input: n = 5, x = 2, y = 1
Output: 32
Explanation:
Each performer will be assigned either stage 1 or stage 2.
All bands will be awarded a score of 1.
Example 3:
Input: n = 3, x = 3, y = 4
Output: 684
Constraints:
1 <= n, x, y <= 1000
Complexity Analysis
- Time Complexity: O(n \cdot \max(n, x))
- Space Complexity: O(n \cdot \max(n, x))
3317. Find the Number of Possible Ways for an Event LeetCode Solution in C++
class Solution {
public:
int numberOfWays(int n, int x, int y) {
const int maxStages = min(n, x);
const auto [fact, invFact] = getFactAndInvFact(max(n, x));
const vector<vector<int>> stirling = getStirling(n, maxStages);
int ans = 0;
for (int k = 1; k <= maxStages; ++k) {
// 1. Choose `k` stages from `x` stages.
long events = nCk(x, k, fact, invFact);
// 2. Partition `n` performers into `k` stages.
events = events * stirling[n][k] % kMod;
// 3. Permute `k` stages.
events = events * fact[k] % kMod;
// 4. Score `k` stages with score in the range [1, y], so y^k ways.
events = events * modPow(y, k) % kMod;
ans = (ans + events) % kMod;
}
return ans;
}
private:
static constexpr int kMod = 1'000'000'007;
pair<vector<long>, vector<long>> getFactAndInvFact(int n) {
vector<long> fact(n + 1);
vector<long> invFact(n + 1);
vector<long> inv(n + 1);
fact[0] = invFact[0] = 1;
inv[0] = inv[1] = 1;
for (int i = 1; i <= n; ++i) {
if (i >= 2)
inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
fact[i] = fact[i - 1] * i % kMod;
invFact[i] = invFact[i - 1] * inv[i] % kMod;
}
return {fact, invFact};
}
int nCk(int n, int k, const vector<long>& fact, const vector<long>& invFact) {
return fact[n] * invFact[k] % kMod * invFact[n - k] % kMod;
}
// Returns a 2D array stirling, where stirling[i][j] := the number of ways to
// partition a set of i objects into j non-empty subsets.
//
// https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
vector<vector<int>> getStirling(int n, int k) {
vector<vector<int>> stirling(n + 1, vector<int>(k + 1));
stirling[0][0] = 1;
for (int i = 1; i <= n; ++i) {
stirling[i][1] = 1;
for (int j = 2; j <= min(i, k); ++j)
stirling[i][j] = (static_cast<long>(j) * stirling[i - 1][j] +
stirling[i - 1][j - 1]) %
kMod;
}
return stirling;
}
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
};
/* code provided by PROGIEZ */3317. Find the Number of Possible Ways for an Event LeetCode Solution in Java
class Solution {
public int numberOfWays(int n, int x, int y) {
final int maxStages = Math.min(n, x);
long[][] factAndInvFact = getFactAndInvFact(Math.max(n, x));
long[] fact = factAndInvFact[0];
long[] invFact = factAndInvFact[1];
int[][] stirling = getStirling(n, maxStages);
int ans = 0;
for (int k = 1; k <= maxStages; ++k) {
// 1. Choose `k` stages from `x` stages.
long events = nCk(x, k, fact, invFact);
// 2. Partition `n` performers into `k` stages.
events = events * stirling[n][k] % kMod;
// 3. Permute `k` stages.
events = events * fact[k] % kMod;
// 4. Score `k` stages with score in the range [1, y], so y^k ways.
events = events * modPow(y, k) % kMod;
ans = (int) ((ans + events) % kMod);
}
return ans;
}
private static final int kMod = 1_000_000_007;
private long[][] getFactAndInvFact(int n) {
long[] fact = new long[n + 1];
long[] invFact = new long[n + 1];
long[] inv = new long[n + 1];
fact[0] = invFact[0] = 1;
inv[0] = inv[1] = 1;
for (int i = 1; i <= n; ++i) {
if (i >= 2)
inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
fact[i] = fact[i - 1] * i % kMod;
invFact[i] = invFact[i - 1] * inv[i] % kMod;
}
return new long[][] {fact, invFact};
}
private int nCk(int n, int k, long[] fact, long[] invFact) {
return (int) (fact[n] * invFact[k] % kMod * invFact[n - k] % kMod);
}
// Returns a 2D array stirling, where stirling[i][j] := the number of ways to
// partition a set of i objects into j non-empty subsets.
//
// https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
private int[][] getStirling(int n, int k) {
int[][] stirling = new int[n + 1][k + 1];
stirling[0][0] = 1;
for (int i = 1; i <= n; ++i) {
stirling[i][1] = 1;
for (int j = 2; j <= Math.min(i, k); ++j)
stirling[i][j] = (int) (((long) j * stirling[i - 1][j] + stirling[i - 1][j - 1]) % kMod);
}
return stirling;
}
private long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x, n - 1) % kMod;
return modPow(x * x % kMod, n / 2);
}
}
// code provided by PROGIEZ3317. Find the Number of Possible Ways for an Event LeetCode Solution in Python
class Solution:
def numberOfWays(self, n: int, x: int, y: int) -> int:
kMod = 1_000_000_007
@functools.lru_cache(None)
def fact(i: int) -> int:
return 1 if i <= 1 else i * fact(i - 1) % kMod
@functools.lru_cache(None)
def inv(i: int) -> int:
return pow(i, kMod - 2, kMod)
@functools.lru_cache(None)
def nCk(n: int, k: int) -> int:
return fact(n) * inv(fact(k)) * inv(fact(n - k)) % kMod
@functools.lru_cache(None)
def stirling(n: int, k: int) -> int:
"""
Returns the number of ways to partition a set of n objects into k
non-empty subsets.
https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind
"""
if k == 0 or n < k:
return 0
if k == 1 or n == k:
return 1
return (k * stirling(n - 1, k) + stirling(n - 1, k - 1)) % kMod
# 1. Choose `k` stages from `x` stages.
# 2. Partition `n` performers into `k` stages.
# 3. Permute `k` stages.
# 4. Score `k` stages with score in the range [1, y], so y^k ways.
return sum(nCk(x, k) * stirling(n, k) * fact(k) * pow(y, k, kMod) % kMod
for k in range(1, min(n, x) + 1)) % kMod
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.