Scale Engineer

Find the Number of Possible Ways for an Event

Hard
#2946Time: O(n * min(n, x)). The nested loops run for `sum_{i=1 to n} min(i, x)` iterations, which simplifies to `O(n*min(n,x))`.Space: O(x) for the space-optimized DP array.
Patterns
MathDynamic ProgrammingCombinatorics

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

We can solve this problem using dynamic programming. We build a solution for n performers based on the solution for n-1 performers. Let dp[i][j] be the number of ways to assign i performers to x stages such that exactly j stages are occupied. We can derive a recurrence relation for dp[i][j]. The final answer is obtained by summing up the ways for all possible numbers of occupied stages, each weighted by the number of ways to assign scores.

Algorithm

  • Let dp[i][j] be the number of ways to assign i performers to x stages, resulting in exactly j occupied stages.
  • The recurrence relation is dp[i][j] = (dp[i-1][j] * j + dp[i-1][j-1] * (x - j + 1)) % MOD.
  • The base case is dp[0][0] = 1.
  • We can use a 1D array dp of size x+1 to optimize space. dp[j] will store the number of ways to assign the current number of performers to occupy j stages.
  • The algorithm proceeds as follows:
    1. Initialize a 1D array dp of size x+1, with dp[0] = 1.
    2. Loop for i from 1 to n (performers).
    3. In an inner loop, update dp[j] for j from min(i, x) down to 1 using the recurrence.
    4. After the loops, dp[j] contains the number of ways to assign n performers to occupy j stages.
    5. The total number of ways is the sum of dp[j] * y^j for j from 1 to min(n, x).
    6. A modular exponentiation function is needed to compute y^j.

Walkthrough

Let dp[i][j] be the number of ways to assign i performers to x stages, resulting in exactly j occupied stages. To compute dp[i][j], we consider the i-th performer. This performer can either be assigned to one of the j stages already occupied by the first i-1 performers, or to one of the x-(j-1) empty stages.

This leads to the recurrence: dp[i][j] = dp[i-1][j] * j + dp[i-1][j-1] * (x - j + 1).

The base case is dp[0][0] = 1 (0 performers, 0 occupied stages, 1 way).

We can build a DP table of size (n+1) x (min(n, x)+1). After computing dp[n][j] for all j from 1 to min(n, x), we can find the total number of ways. For a fixed j, there are dp[n][j] ways to form j bands. Each of these j bands can be awarded a score from 1 to y, giving y^j ways to assign scores.

The total number of ways is sum_{j=1 to min(n, x)} (dp[n][j] * y^j).

All calculations should be done modulo 10^9 + 7. The space complexity can be optimized from O(n*x) to O(x) by noticing that dp[i] only depends on dp[i-1], allowing for an in-place update.

class Solution {    long MOD = 1_000_000_007;     public int numberOfWays(int n, int x, int y) {        long[] dp = new long[x + 1];        dp[0] = 1;         for (int i = 1; i <= n; i++) {            for (int j = Math.min(i, x); j >= 1; j--) {                long term1 = (dp[j] * j) % MOD;                long term2 = (dp[j - 1] * (x - j + 1)) % MOD;                dp[j] = (term1 + term2) % MOD;            }        }         long totalWays = 0;        for (int j = 1; j <= Math.min(n, x); j++) {            long waysForJStages = dp[j];            long scoreWays = power(y, j);            totalWays = (totalWays + (waysForJStages * scoreWays) % MOD) % MOD;        }         return (int) totalWays;    }     private long power(long base, long exp) {        long res = 1;        base %= MOD;        while (exp > 0) {            if (exp % 2 == 1) res = (res * base) % MOD;            base = (base * base) % MOD;            exp /= 2;        }        return res;    }}

Complexity

Time

O(n * min(n, x)). The nested loops run for `sum_{i=1 to n} min(i, x)` iterations, which simplifies to `O(n*min(n,x))`.

Space

O(x) for the space-optimized DP array.

Trade-offs

Pros

  • Relatively simple to understand and implement.

  • The logic follows a natural step-by-step build-up.

Cons

  • It is asymptotically slower than the combinatorial approach, especially when n is much larger than x.

Solutions

class Solution {public  int numberOfWays(int n, int x, int y) {    final int mod = (int)1 e9 + 7;    long[][] f = new long[n + 1][x + 1];    f[0][0] = 1;    for (int i = 1; i <= n; ++i) {      for (int j = 1; j <= x; ++j) {        f[i][j] =            (f[i - 1][j] * j % mod + f[i - 1][j - 1] * (x - (j - 1) % mod)) %            mod;      }    }    long ans = 0, p = 1;    for (int j = 1; j <= x; ++j) {      p = p * y % mod;      ans = (ans + f[n][j] * p) % mod;    }    return (int)ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem