Dice rolls with a target sum
Medium · Target 20 minutes · Dynamic programming · Type asked atAmazonTwo Sigma
Jane Street
You roll n dice, each with faces 1 to k. Return the number of ordered outcomes (one face per
die) whose sum is target, modulo 10⁹ + 7.
Examples
| Input | Output | Why |
|---|---|---|
n = 1, k = 6, target = 3 | 1 | Roll a 3. |
n = 2, k = 6, target = 7 | 6 | 1+6, 2+5, 3+4, 4+3, 5+2, 6+1. |
n = 30, k = 30, target = 500 | 222616187 | Modulo 10⁹ + 7. |
Constraints
- 1 ≤ n, k ≤ 30
- 1 ≤ target ≤ 1000
Hints
Hint 1
The state needs the number of dice rolled, not just the sum: ways[d][s].
Hint 2
ways[d][s] = Σ over faces f of ways[d − 1][s − f].
Hint 3
Keep one row per die; reduce modulo 10⁹ + 7 after every addition.
Where people lose marks
- Dropping the dice count from the state, which allows any number of dice.
- Forgetting the modulus until the end, which overflows.
- Counting unordered outcomes.
Dry run on 2,6,7
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 30 dice1001020304050607
With no dice, only the sum 0 is possible.
-
Step 2 / 31 dice0011121314151607
After die 1: each sum adds the ways for the sums 1 to 6 below it.
-
Step 3 / 32 dice0001122334455667
After die 2: each sum adds the ways for the sums 1 to 6 below it. 6 ways to make 7.
How to think about it
A counting knapsack with an exact number of picks, so the state is (dice rolled, sum so far). Each die adds a face from
1 to k: ways[d][s] = Σ ways[d − 1][s − f], with ways[0][0] = 1. One row per die suffices. The inner
sum can be maintained as a sliding window of the previous row to make each row O(target), though O(target · k) is fine at
these sizes.
Complexity. Time O(n · target · k) · Space O(target)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def num_rolls_to_target(n, k, target):
MOD = 10**9 + 7
ways = [1] + [0] * target # zero dice: only the sum 0
for _ in range(n):
new = [0] * (target + 1)
for s in range(1, target + 1):
for f in range(1, min(k, s) + 1):
new[s] = (new[s] + ways[s - f]) % MOD # this die shows f
ways = new
return ways[target]#include <vector>
long long solve(int n, int k, int target) {
const long long MOD = 1000000007;
std::vector<long long> ways(target + 1, 0), next(target + 1);
ways[0] = 1;
for (int d = 0; d < n; ++d) {
next.assign(target + 1, 0);
for (int s = 1; s <= target; ++s)
for (int f = 1; f <= k && f <= s; ++f) next[s] = (next[s] + ways[s - f]) % MOD;
ways.swap(next);
}
return ways[target];
}class Solution {
public long numRollsToTarget(int n, int k, int target) {
final long MOD = 1_000_000_007L;
long[] ways = new long[target + 1];
ways[0] = 1;
for (int d = 0; d < n; d++) {
long[] next = new long[target + 1];
for (int s = 1; s <= target; s++)
for (int f = 1; f <= k && f <= s; f++) next[s] = (next[s] + ways[s - f]) % MOD;
ways = next;
}
return ways[target];
}
}function numRollsToTarget(n, k, target) {
const MOD = 1000000007;
let ways = [1, ...new Array(target).fill(0)];
for (let d = 0; d < n; d++) {
const next = new Array(target + 1).fill(0);
for (let s = 1; s <= target; s++)
for (let f = 1; f <= k && f <= s; f++) next[s] = (next[s] + ways[s - f]) % MOD; // this die shows f
ways = next;
}
return ways[target];
}fn solve(n: i64, k: i64, target: i64) -> i64 {
const MOD: i64 = 1_000_000_007;
let t = target as usize;
let mut ways = vec![0i64; t + 1];
ways[0] = 1;
for _ in 0..n {
let mut next = vec![0i64; t + 1];
for s in 1..=t {
for f in 1..=(k as usize).min(s) {
next[s] = (next[s] + ways[s - f]) % MOD; // this die shows f
}
}
ways = next;
}
ways[t]
}solve :: Int -> Int -> Int -> Int
solve n k target = iterate roll (1 : replicate target 0) !! n !! target
where
modulus = 1000000007
-- one more die: each sum s collects the old ways for s - 1 .. s - k
roll ways = [if s == 0 then 0 else sum [ways !! (s - f) | f <- [1 .. min k s]] `mod` modulus | s <- [0 .. target]]Variants to try
- The probability that the sum exceeds a threshold.
- Each die has its own number of faces.
- Use a sliding window to make it O(n · target).
Next problems
Ordered ways to reach a total
Count the ordered sequences of numbers, each usable any number of times, that sum to a target. The same loops as coin change, swapped.
Open the problem → Medium15 minSubsets with a given sum
Count the subsets of a list (by position) that add up to the target. The 0/1 knapsack with sum: totals downwards, each element at most once.
Open the problem → Easy10 minThe cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem →Write a solution and run it against the real test table.
Keep going
Ordered ways to reach a total
Count the ordered sequences of numbers, each usable any number of times, that sum to a target. The same loops as coin change, swapped.
Open the problem → Medium15 minSubsets with a given sum
Count the subsets of a list (by position) that add up to the target. The 0/1 knapsack with sum: totals downwards, each element at most once.
Open the problem → Easy10 minThe cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.