We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Dice Rolls With Target Sum

Number: 1263

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Adobe

Problem Description

Given n dice, each having k faces numbered from 1 to k, determine the number of ways to roll the dice such that the sum of the top faces equals target. Since the answer can be very large, return the result modulo 10^9 + 7.

Key Insights

  • Use dynamic programming to build the solution iteratively.
  • Define dp[i][j] as the number of ways to achieve sum j using i dice.
  • The base case is dp[0][0] = 1, representing one way to achieve a sum of 0 using 0 dice.
  • For each die, consider all possible face values from 1 to k, and update the dp table accordingly.
  • Only update for sums that remain within the target.
  • The final answer will be stored in dp[n][target] modulo 10^9 + 7.

Space and Time Complexity

Time Complexity: O(n * target * k)
Space Complexity: O(target) if optimized using a one-dimensional dp array.

Solution

We solve the problem using a dynamic programming approach. A one-dimensional dp array is maintained where dp[j] represents the number of ways to obtain the sum j using the current number of dice. We start with dp[0] = 1 since there is exactly one way to achieve a sum of 0 without using any dice. For each dice, a new dp array is computed by iterating over every possible current sum and adding each possible dice face value (from 1 to k) if the new sum does not exceed target. By repeatedly updating the dp array, we obtain the final count in dp[target] after processing all dice. We take every update modulo 10^9 + 7 to handle large numbers.

Code Solutions

# Function to compute the number of ways to roll dice to achieve the target sum
def numRollsToTarget(n, k, target):
    MOD = 10**9 + 7
    # dp[j] will represent the number of ways to form sum j using the given dice
    dp = [0] * (target + 1)
    dp[0] = 1  # Base case: 1 way to reach sum 0 with no dice
    
    # Process each dice
    for dice in range(1, n + 1):
        next_dp = [0] * (target + 1)
        # for each possible current sum
        for prev_sum in range(target + 1):
            if dp[prev_sum] != 0:
                # Try every face value on the current dice
                for face in range(1, k + 1):
                    current_sum = prev_sum + face
                    if current_sum <= target:
                        next_dp[current_sum] = (next_dp[current_sum] + dp[prev_sum]) % MOD
        dp = next_dp  # update dp for the next dice
    return dp[target]

# Example test cases
print(numRollsToTarget(1, 6, 3))    # Expected output: 1
print(numRollsToTarget(2, 6, 7))    # Expected output: 6
print(numRollsToTarget(30, 30, 500))# Expected output: 222616187
← Back to All Questions