Ctrl K

Ways to Roll a Sum

Medium
You have dice identical dice, each with faces numbered 1 to faces. All of them are rolled at once and the numbers that come up are added together. The dice are distinguishable: a roll is defined by the number on the first die, the number on the second, and so on, so there are faces to the power of dice possible rolls. Return how many of them add up to exactly total. The answer can be huge, so return it modulo 10⁹ + 7.
Example 1
dice=2, faces=4, total=5 → 4

The rolls 1+4, 2+3, 3+2 and 4+1 work: four of them. The dice are distinguishable, so 1+4 and 4+1 count separately.

Example 2
dice=3, faces=2, total=7 → 0

Three two-sided dice can show at most 6, so 7 is impossible.

Example 3
dice=25, faces=20, total=260 → 255576909
Constraints
  • 1 ≤ dice, faces ≤ 30
  • 1 ≤ total ≤ 1000
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsLongest Mirror Fragment MediumAll Balanced Bracket Strings MediumFewest Jumps to the End MediumMost Profitable Streak MediumReach the Last Cell Medium
loading Python…
Input
dice=2, faces=4, total=5
Expected
4

Run checks the first 3 tests in your browser. Submit checks all 111 tests on the server, hidden ones included.