Scale Engineer

Number of Dice Rolls With Target Sum

Med
#1086Time: O(k^n) - The recursion tree has a depth of `n`, and each function call branches `k` times. This leads to an exponential number of calls, making it infeasible for the given constraints.Space: O(n) - The space is dominated by the maximum depth of the recursion stack, which is equal to the number of dice `n`.1 company
Patterns
Dynamic Programming
Companies
StackAdapt

Prompt

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 <= 30
  • 1 <= target <= 1000

Approaches

5 approaches with complexity analysis and trade-offs.

The most intuitive approach is to simulate all possible outcomes of rolling n dice. We can use a recursive function to explore every combination. The function's state can be defined by the number of dice remaining to be rolled and the remaining target sum.

Algorithm

  • Define a recursive function solve(d, t) that returns the number of ways to get sum t with d dice.
  • Base Case 1: If d == 0 and t == 0, a valid combination is found. Return 1.
  • Base Case 2: If d == 0 or t <= 0, it's an impossible path. Return 0.
  • Recursive Step: Iterate through each possible face value f from 1 to k. For each f, make a recursive call solve(d - 1, t - f).
  • Sum up the results from all recursive calls, taking the modulo at each step.
  • The initial call is solve(n, target).

Walkthrough

We define a recursive function, say solve(d, t), which calculates the number of ways to get a sum t using d dice. The base case for the recursion is when we have no dice left (d == 0). If the target sum is also zero (t == 0), we have found one valid way. Otherwise, it's an invalid path. In the recursive step, for the current die, we iterate through all possible face values from 1 to k. For each face value f, we make a recursive call with one less die and a reduced target sum: solve(d - 1, t - f). The total number of ways is the sum of the results from these recursive calls. The initial call to the function would be solve(n, target). This method explores the entire search space, which grows exponentially.

class Solution {    private static final int MOD = 1_000_000_007;     public int numRollsToTarget(int n, int k, int target) {        // Early exit for impossible targets        if (target < n || target > n * k) {            return 0;        }        return solve(n, k, target);    }     private int solve(int n, int k, int remainingTarget) {        // Base case: If we have used all dice        if (n == 0) {            // If the target is also 0, we found a valid combination            return remainingTarget == 0 ? 1 : 0;        }         // If remaining target is impossible to achieve with remaining dice        if (remainingTarget <= 0) {            return 0;        }         int ways = 0;        // Try each possible face for the current die        for (int face = 1; face <= k; face++) {            // Recur for the next die with the reduced target            ways = (ways + solve(n - 1, k, remainingTarget - face)) % MOD;        }        return ways;    }}

Complexity

Time

O(k^n) - The recursion tree has a depth of `n`, and each function call branches `k` times. This leads to an exponential number of calls, making it infeasible for the given constraints.

Space

O(n) - The space is dominated by the maximum depth of the recursion stack, which is equal to the number of dice `n`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly models the problem's logic.

Cons

  • Extremely inefficient due to exponential time complexity.

  • Will result in a 'Time Limit Exceeded' error for most constraints beyond the smallest examples.

Solutions

class Solution {public  int numRollsToTarget(int n, int k, int target) {    final int mod = (int)1 e9 + 7;    int[][] f = new int[n + 1][target + 1];    f[0][0] = 1;    for (int i = 1; i <= n; ++i) {      for (int j = 1; j <= Math.min(target, i * k); ++j) {        for (int h = 1; h <= Math.min(j, k); ++h) {          f[i][j] = (f[i][j] + f[i - 1][j - h]) % mod;        }      }    }    return f[n][target];  }}

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