Number of Dice Rolls With Target Sum - Practice Coding Problems

Number of Dice Rolls With Target Sum - Problem

Dynamic Programming Medium

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 k^n 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 10^9 + 7.

Input & Output

Example 1 — Basic Case

$ Input: n = 1, k = 6, target = 3

› Output: 1

💡 Note: With 1 die having 6 faces, only one way to get sum 3: roll a 3

Example 2 — Multiple Ways

$ Input: n = 2, k = 6, target = 7

› Output: 6

💡 Note: With 2 dice, 6 ways to get sum 7: (1,6), (2,5), (3,4), (4,3), (5,2), (6,1)

Example 3 — Impossible Target

$ Input: n = 30, k = 30, target = 500

› Output: 222616187

💡 Note: Large case with many combinations, result modulo 10^9 + 7

Constraints

1 ≤ n, k ≤ 30
1 ≤ target ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

n=2 dice, k=6 faces each, target=7

Process

Find all valid combinations that sum to target

Output

Count = 6 different ways

Key Takeaway

🎯 Key Insight: Use dynamic programming to build up solutions for smaller subproblems and combine them efficiently

Asked in

a Amazon 15 G Google 12 M Microsoft 8

This problem uses dynamic programming to count ways to achieve a target sum with dice rolls. The key insight is that each state depends on the number of dice remaining and the current sum. Best approach is 1D space-optimized DP. Time: O(n × target × k), Space: O(target).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(k^n)	O(n)	Try all possible dice combinations recursively
Space-Optimized 1D Dynamic Programming	O(n × target × k)	O(target)	Optimize space by using only current and previous row
Memoization (Top-Down DP)	O(n × target × k)	O(n × target)	Cache results of recursive calls to avoid recomputation
Bottom-Up 2D Dynamic Programming	O(n × target × k)	O(n × target)	Build solution table from base cases up to final answer

Brute Force Recursion — Algorithm Steps

Try each face value (1 to k) for current die
Recursively count ways for remaining dice with updated target
Sum up all valid combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with n dice and target sum

Branch

Try each face value (1 to k) for current die

Recurse

Continue with remaining dice and updated target

Code -

solution.c — C

#include <stdio.h>

const int MOD = 1000000007;

int backtrack(int diceLeft, int currentSum, int k, int target) {
    if (diceLeft == 0) {
        return currentSum == target ? 1 : 0;
    }
    if (currentSum > target) {
        return 0;
    }
    
    long long ways = 0;
    for (int face = 1; face <= k; face++) {
        ways = (ways + backtrack(diceLeft - 1, currentSum + face, k, target)) % MOD;
    }
    return ways;
}

int solution(int n, int k, int target) {
    return backtrack(n, 0, k, target);
}

int main() {
    int n, k, target;
    scanf("%d %d %d", &n, &k, &target);
    printf("%d\n", solution(n, k, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

Each of n dice has k choices, creating k^n total combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth equals number of dice

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler