Number of Dice Rolls With Target Sum
#528 Most AskedMedium
Number of Dice Rolls With Target Sum #528 Most Asked
Medium
2 views
Topics:
Dynamic ProgrammingRecursion
You have n dice, and each dice has k faces numbered from 1 to k.
Given three integers n, k, and target, return the number of possible ways (out of the kn total ways) to roll the dice, so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: n = 1, k = 6, target = 3 Output: 1 Explanation: You throw one die with 6 faces. There is only one way to get a sum of 3.
Example 2:
Input: n = 2, k = 6, target = 7 Output: 6 Explanation: You throw two dice, each with 6 faces. There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.
Example 3:
Input: n = 30, k = 30, target = 500 Output: 222616187 Explanation: The answer must be returned modulo 109 + 7.
Constraints:
1 <= n, k <= 301 <= target <= 1000
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What are the constraints on `n`, `k`, and `target`? Specifically, what are the maximum and minimum values for each?
- Is it possible for `target` to be negative or zero?
- If it's impossible to reach the `target` with the given `n` and `k`, what should the function return? Should it return 0, null, or throw an exception?
- Should the result be returned modulo some number? If so, what is that number?
- Are we only interested in the number of ways to reach the target, or do we need to return the actual combinations of dice rolls?
Brute Force Solution
Approach
The brute force approach to this dice problem is to try every possible combination of dice rolls. We explore every single way we can roll the dice to see if it adds up to our target number. It's like trying every single combination lock code until you find the right one.
Here's how the algorithm would work step-by-step:
- Consider the first die. It can show any number from 1 up to the maximum number on a die (usually 6).
- For each possible number on the first die, consider the second die. It can also show any number from 1 up to the maximum.
- Keep repeating this for each die. So, for each combination of numbers on the first and second dice, consider all possible numbers on the third die, and so on.
- After you've assigned a value to each die, add up all the numbers.
- If the sum equals the target number, count that as one possible way to reach the target.
- If the sum does NOT equal the target number, discard that combination and move on to trying the next possible set of dice rolls.
- Continue trying every possible combination of dice rolls until you have explored absolutely every possibility. At the end, you'll have a count of all the combinations that add up to the target number.
Code Implementation
def number_of_dice_rolls_with_target_sum_brute_force(
number_of_dice, number_of_faces, target_sum
):
number_of_ways = 0
def solve(dice_index, current_sum):
nonlocal number_of_ways
# If we've used all the dice, check if we've reached the target
if dice_index == number_of_dice:
if current_sum == target_sum:
number_of_ways += 1
return
# Iterate through all possible values for the current die
for face_value in range(1, number_of_faces + 1):
# Recursively call with next die and updated sum
solve(dice_index + 1, current_sum + face_value)
# Initiate recursive calls, starting with the first die
solve(0, 0)
return number_of_waysBig(O) Analysis
Time Complexity
O(k^n) – The brute force approach explores all possible combinations of dice rolls. We have 'n' dice, and each die can show a number from 1 to 'k' (the number of faces on the die). Therefore, each die has 'k' possibilities. Since we have 'n' dice, we have k * k * k ... (n times) which is k^n possible combinations. Consequently, the algorithm must explore all k^n combinations, making the time complexity O(k^n).
Space Complexity
O(K) – The brute force approach uses recursion. The depth of the recursion depends on the number of dice, K. Each recursive call adds a new frame to the call stack to store the current die, the current sum, and the target. Therefore, the maximum depth of the recursion is K, leading to a call stack of size O(K).
Optimal Solution
Approach
The most efficient way to solve this problem is to break it down into smaller, overlapping subproblems and remember the solutions. This prevents us from recalculating the same thing multiple times. Think of it like building a table of answers to reuse later.
Here's how the algorithm would work step-by-step:
- Imagine you have a table where each cell represents the number of ways to reach a certain total using a certain number of dice.
- Start by filling in the easy parts of the table. For example, if you have zero dice, there's only one way to reach a total of zero.
- Then, for each cell, consider what the last dice roll could have been. It could have been a 1, 2, 3, up to the maximum number on the dice.
- Look up the number of ways to reach the remaining total using one fewer dice for each possible last roll.
- Add those numbers together to get the number of ways to reach the current total with the current number of dice.
- Store this number in the current cell of the table.
- Continue filling in the table until you reach the cell that represents the target total and the given number of dice. This cell will contain the answer.
Code Implementation
def num_rolls_to_target(number_of_dice, number_of_faces, target_sum):
ways_to_sum = [[0] * (target_sum + 1) for _ in range(number_of_dice + 1)]
ways_to_sum[0][0] = 1
# Base case: One way to get zero sum using zero dice.
for current_dice_count in range(1, number_of_dice + 1):
for current_target_value in range(1, target_sum + 1):
# Iterate through possible face values of the current die
for current_face_value in range(1, number_of_faces + 1):
if current_target_value >= current_face_value:
# Adding previous possible outcomes.
ways_to_sum[current_dice_count][current_target_value] += ways_to_sum[current_dice_count - 1][current_target_value - current_face_value]
# The result is the number of ways to reach the target sum
return ways_to_sum[number_of_dice][target_sum] % (10**9 + 7)Big(O) Analysis
Time Complexity
O(d * target * n) – The algorithm uses dynamic programming, constructing a table to store intermediate results. The table has dimensions n (number of dice) by target (target sum). For each cell in the table, we iterate up to d (number of faces on the die). Therefore, we perform calculations on each cell that costs O(d) time. The overall time complexity is determined by the number of cells in the table, and the work done in each cell, giving O(d * target * n).
Space Complexity
O(target * d) – The solution uses a table (dynamic programming table) to store the number of ways to reach a certain total using a certain number of dice. The dimensions of this table are determined by the target value and the number of dice, d. Specifically, the table will have dimensions (d+1) x (target+1). Therefore, the auxiliary space required to store this table is proportional to the product of the number of dice, d, and the target value. Thus, the space complexity is O(target * d).
Edge Cases
| Case | How to Handle |
|---|---|
| n = 0 (no dice) | If n is 0, and the target is also 0, return 1 (one way to achieve a sum of 0 with 0 dice); otherwise, return 0. |
| k = 0 (no faces) | If k is 0, it's impossible to roll a positive sum, so return 0 unless target is also 0 (which is impossible with positive number of dice). |
| target = 0 | If target is 0 and n is greater than 0, the only way to get 0 sum is if all dice are 0 which is impossible, return 0. |
| target < 0 | Return 0 immediately as it's impossible to achieve a negative target sum with positive dice values. |
| n = 1, target > k | Return 0 because it's impossible to reach the target with a single die with 'k' faces. |
| target > n * k (target exceeds max possible sum) | Return 0 because the target is impossible to reach with the given number of dice and faces. |
| Large n, k, or target values leading to integer overflow | Apply modulo operation (10^9 + 7) after each intermediate calculation to prevent integer overflow. |
| n and k are large, potentially causing stack overflow with naive recursion | Use dynamic programming (memoization or tabulation) to avoid excessive recursion depth and potential stack overflow. |
n = 0 (no dice)
How to Handle:
If n is 0, and the target is also 0, return 1 (one way to achieve a sum of 0 with 0 dice); otherwise, return 0.
k = 0 (no faces)
How to Handle:
If k is 0, it's impossible to roll a positive sum, so return 0 unless target is also 0 (which is impossible with positive number of dice).
target = 0
How to Handle:
If target is 0 and n is greater than 0, the only way to get 0 sum is if all dice are 0 which is impossible, return 0.
target < 0
How to Handle:
Return 0 immediately as it's impossible to achieve a negative target sum with positive dice values.
n = 1, target > k
How to Handle:
Return 0 because it's impossible to reach the target with a single die with 'k' faces.
target > n * k (target exceeds max possible sum)
How to Handle:
Return 0 because the target is impossible to reach with the given number of dice and faces.
Large n, k, or target values leading to integer overflow
How to Handle:
Apply modulo operation (10^9 + 7) after each intermediate calculation to prevent integer overflow.
n and k are large, potentially causing stack overflow with naive recursion
How to Handle:
Use dynamic programming (memoization or tabulation) to avoid excessive recursion depth and potential stack overflow.
0/1037 Bloomberg LP questions completed
0/1037 completed
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
