Skip to main content
Talentd

Find the Number of Possible Ways for an Event - Solution & Explanation

HardMathDynamic ProgrammingCombinatorics21 min readAsked at: Amazon
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You have n participants, x available stages, and y possible score values for each stage. Participants are distributed across stages such that every used stage has at least one participant. Each used stage then receives one of the y score values. The task is to count the total number of valid configurations modulo 1e9+7.

The key observation: if exactly k stages are used, three independent choices happen. First distribute n participants into k non‑empty groups. Then map those groups to k distinct stages out of x. Finally assign a score to each used stage. Summing this count for all valid k gives the final answer.

Approach 1: Combinatorial Counting with Stirling Numbers (Time: O(n * min(n,x)), Space: O(n * min(n,x)))

This approach models the distribution of participants using Stirling numbers of the second kind. S(n, k) represents the number of ways to partition n items into k non‑empty groups. Once groups are formed, map them to k distinct stages using permutations P(x, k). Each used stage independently chooses a score from y possibilities, giving y^k choices. The total for a fixed k becomes S(n,k) * P(x,k) * y^k. Iterate k from 1 to min(n, x), accumulate the values modulo 1e9+7. This method relies heavily on combinatorics and factorial-based permutations.

Approach 2: Dynamic Programming for Stirling Numbers (Time: O(n * min(n,x)), Space: O(n * min(n,x)))

Instead of using a direct combinatorial formula, compute S(n,k) using the recurrence S(n,k) = S(n-1,k-1) + k * S(n-1,k). Build a DP table where rows represent participants and columns represent group counts. Each state represents how many ways participants can form k non‑empty groups. After computing the DP table, combine each S(n,k) with the permutation term P(x,k) and the scoring term y^k. Modular exponentiation handles the y^k factor efficiently. This formulation fits naturally with dynamic programming and avoids needing precomputed Stirling values.

Recommended for interviews: The combinatorial formulation with Stirling numbers is what interviewers usually expect for a hard counting problem involving labeled resources and non‑empty partitions. Showing the DP recurrence for S(n,k) demonstrates deeper understanding of math and combinatorial identities. Brute enumeration is infeasible due to exponential growth, so recognizing the partition‑then‑assign structure is the real insight.

Approach 1: Combinatorial Approach

This approach focuses on understanding the number of ways performers can be assigned to different stages and the number of scoring possibilities for the bands. We calculate the number of ways to assign performers to stages as x^n and multiply it by the number of scoring combinations for each band, which is y^x. Finally, result modulo 10^9 + 7 is returned.

This C solution computes the number of ways to assign performers to stages using power_mod, which calculates base^exp % mod. The final result is derived by multiplying the number of stage assignments and scoring combinations, then taking the modulus.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n + log x) due to modular exponentiation.
Space Complexity: O(1).

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

This approach utilizes dynamic programming to calculate the number of ways to assign performers to stages while also keeping track of scored bands. The idea is to build up a solution incrementally using previously computed results, which can be especially useful in cases where recursive approaches might lead to computation of the same sub-problems.

This C solution uses a dynamic programming array to keep track of ways performers can be assigned to stages. It iteratively fills this array, using previously computed values to build the solution dynamically.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + x)
Space Complexity: O(n).

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i][j] to represent the number of ways to arrange the first i performers into j programs. Initially, f[0][0] = 1, and the rest f[i][j] = 0.

For f[i][j], where 1 leq i leq n and 1 leq j leq x, we consider the i-th performer:

  • If the performer is assigned to a program that already has performers, there are j choices, i.e., f[i - 1][j] times j;
  • If the performer is assigned to a program that has no performers, there are x - (j - 1) choices, i.e., f[i - 1][j - 1] times (x - (j - 1)).

So the state transition equation is:

$ f[i][j] = f[i - 1][j] times j + f[i - 1][j - 1] times (x - (j - 1))

For each j, there are y^j choices, so the final answer is:

sum_{j = 1}^{x} f[n][j] times y^j

Note that since the answer can be very large, we need to take the modulo 10^9 + 7.

The time complexity is O(n times x), and the space complexity is O(n times x). Here, n and x$ represent the number of performers and the number of programs, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Combinatorial Approach

Time Complexity: O(log n + log x) due to modular exponentiation.
Space Complexity: O(1).

Dynamic Programming Approach

Time Complexity: O(n + x)
Space Complexity: O(n).

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Combinatorial Counting with Stirling NumbersO(n · min(n,x))O(n · min(n,x))Best general solution when using combinatorics and modular arithmetic
Dynamic Programming for Stirling NumbersO(n · min(n,x))O(n · min(n,x))Useful when deriving Stirling values directly with DP

Video Solution

Leetcode Biweekly Contest 141 | 3317. Find the Number of Possible Ways for an Event | Codefod • CodeFod • 659 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Find the Number of Possible Ways for an Event easy or hard?
LeetCode classifies this problem as Hard. It requires recognizing the partition structure, applying Stirling numbers of the second kind, and combining them with permutations and modular exponentiation.
Find the Number of Possible Ways for an Event Python/Java solution
Python and Java implementations typically build a DP table for Stirling numbers, then iterate over k from 1 to min(n,x). Each term S(n,k) is multiplied by P(x,k) and pow(y,k,MOD) to accumulate the final answer under modulo 1e9+7.
How to solve Find the Number of Possible Ways for an Event in O(n)?
An exact O(n) solution generally isn't used because the computation requires values for multiple k up to min(n,x). The practical optimal approach computes Stirling numbers with DP in O(n·min(n,x)) time, then combines them with permutations and fast exponentiation.
What is the best approach for Find the Number of Possible Ways for an Event?
The best approach uses combinatorics with Stirling numbers of the second kind. For each possible number of used stages k, compute S(n,k) ways to partition participants, multiply by P(x,k) ways to map groups to stages, and multiply by y^k score assignments. Summing over k from 1 to min(n,x) gives the answer in O(n·min(n,x)) time.
Is Find the Number of Possible Ways for an Event asked at Google/Amazon/Meta?
This style of problem appears in interviews at companies like Google, Amazon, and Meta when testing advanced counting techniques. It combines combinatorics, dynamic programming, and modular arithmetic, which are common in senior-level algorithm interviews.
What data structure is used in Find the Number of Possible Ways for an Event?
The core structure is a dynamic programming table used to compute Stirling numbers S(n,k). Along with this table, the solution relies on factorial or permutation calculations and fast modular exponentiation for the y^k term.
What is the time complexity of Find the Number of Possible Ways for an Event?
The typical solution runs in O(n · min(n, x)) time. This cost comes from computing Stirling numbers S(n,k) using dynamic programming and iterating over all possible values of k. Space complexity is also O(n · min(n,x)) for the DP table.

Ready to solve this problem?

Practice Find the Number of Possible Ways for an Event with our built-in code editor and test cases.

Practice on FleetCode
Previous

Kth Smallest Amount With Single Denomination Combination