1155. Number of Dice Rolls With Target Sum LeetCode Solution
In this guide, you will get 1155. Number of Dice Rolls With Target Sum LeetCode Solution with the best time and space complexity. The solution to Number of Dice Rolls With Target Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Dice Rolls With Target Sum
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.
1155. Number of Dice Rolls With Target Sum LeetCode Solution in C++
class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
constexpr int kMod = 1'000'000'007;
vector<int> dp(target + 1);
dp[0] = 1;
while (n-- > 0) { // n dices
vector<int> newDp(target + 1);
for (int i = 1; i <= k; ++i) // numbers 1, 2, ..., f
for (int t = i; t <= target; ++t) { // all the possible targets
newDp[t] += dp[t - i];
newDp[t] %= kMod;
}
dp = std::move(newDp);
}
return dp[target];
}
}; /* code provided by PROGIEZ */
1155. Number of Dice Rolls With Target Sum LeetCode Solution in Java
class Solution {
public int numRollsToTarget(int n, int k, int target) {
final int kMod = 1_000_000_007;
int[] dp = new int[target + 1];
dp[0] = 1;
while (n-- > 0) { // n dices
int[] newDp = new int[target + 1];
for (int i = 1; i <= k; ++i) // numbers 1, 2, ..., f
for (int t = i; t <= target; ++t) { // all the possible targets
newDp[t] += dp[t - i];
newDp[t] %= kMod;
}
dp = newDp;
}
return dp[target];
}
} // code provided by PROGIEZ
1155. Number of Dice Rolls With Target Sum LeetCode Solution in Python
class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
kMod = 1_000_000_007
dp = [1] + [0] * target
for _ in range(n): # n dices
newDp = [0] * (target + 1)
for i in range(1, k + 1): # numbers 1, 2, ..., f
for t in range(i, target + 1): # all the possible targets
newDp[t] += dp[t - i]
newDp[t] %= kMod
dp = newDp
return dp[target] # code by PROGIEZ
