1155. Number of Dice Rolls With Target Sum
Problem Description
In this problem, we are working with a scenario involving n dice, each having k faces numbered from 1 to k. We want to figure out how many different ways we can roll these dice so that the sum of the numbers showing on the tops of all dice equals a specific target value. To clarify, there are a total of k^n different roll combinations since each die can land on any of its k faces and we have n dice in total. The challenge is to filter out and count only those combinations where the sum equals target. Because the number of possible ways can get extremely large, the result should be provided modulo 10^9 + 7 to avoid overflow issues.
Intuition
The core of the solution lies in dynamic programming, a method that involves breaking down a complex problem into smaller, more manageable subproblems and building up the solution from the answers to these subproblems.
The main idea is to keep track of the number of ways to achieve a certain sum using a particular number of dice. To do this, we define a state f[i][j], which represents the count of ways to reach a sum of j using i dice. We start from the base case where no dice are used, so the only possible sum of zero is to have zero dice (which is one way).
From there, we incrementally build up by considering one more die at each step. For every number of dice i from 1 to n and for each possible sum j up to the target, we determine the number of ways to achieve that sum by considering all the possible outcomes of the new die. In simple terms, for every possible value h that the new die could land on, we add the number of ways to achieve the sum j - h using i - 1 dice to our current count.
Through these iterations, we build a table of values reflecting the different ways to reach the sum, all the way up to using all n dice to reach the target sum. The final answer is then the value stored in f[n][target].
The given solution cleverly optimizes the space complexity by using a single-dimensional array f[], where the values of the previous iteration are used to calculate the values of the current iteration. As each value is computed, it is stored back in f[] after considering all possible faces of the current die. This is done to ensure that we are neither running out of memory due to a large number of subproblems nor repeating the calculation for the same subproblems multiple times.
Learn more about Dynamic Programming patterns.
Which of these properties could exist for a graph but not a tree?
Solution Approach
The implementation of the solution involves a two-dimensional problem being solved using a one-dimensional array to save space. The mathematical formula that guides the solution is:
1f[i][j] = sum(f[i-1][j-h] for h in range(1, min(j, k)+1))
This equation is the heart of our dynamic programming approach, where f[i][j] is the number of ways to get a sum of j using i dice. However, instead of using a two-dimensional array, we optimize the solution by reusing a single array f where f[j] at any point contains the number of ways to reach sum j with the current number of dice considered.
The innermost loop runs through all the possible face values (h) of the current die (up to k, but not more than j since we can't have the face value of a die be more than the sum we're trying to achieve). For each face value, it adds to the temporary array g[j] the number of ways we can achieve the remaining sum (j - h) with one less die, modulo 10^9 + 7 to prevent overflow.
After each die is considered (outer loop), the f array is updated to be the temporary array g for the next iteration, effectively moving from analyzing i-1 dice to i dice while preserving the required state and avoiding the direct use of a two-dimensional array.
Here is an implementation perspective that breaks down each part of the code:
-
Initialization: An array
fis initialized with sizetarget + 1, starting withf[0] = 1and the rest0. This reflects the base case where a sum of0can be achieved in one way with zero dice. -
Building up solutions for each die:
- A temporary array
gis initialized to hold the number of ways to reach every possible sum up totargetwith one additional die. - We iterate over each sum
jthat could be reached with the current number (i) of dice. - For each
j, we calculateg[j]based on previous sums computed inf.
- A temporary array
-
Updating state: After considering all sums for the current die, we make
f = gto update our state without using additional space for a second dimension. -
Return the answer: After considering all
ndice,f[target]gives us the final number of ways to reach thetargetsum. -
Modulus Operation: A
modconstant is used at each step of the calculation to ensure the number stays within the specified range,10^9 + 7.
By iterating through dice and potential sums in this manner, the dynamic programming approach efficiently calculates the number of ways to roll the dice to reach a targeted sum.
What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Example Walkthrough
Let's illustrate the solution approach using an example where we have n = 2 dice and each die has k = 3 faces numbered from 1 to 3. We want to find out how many ways we can roll the dice so that the sum is equal to the target value of 4.
-
Initialization: We initialize an array
fwith a length oftarget + 1, which meansfhas a size of 5 in this case (0, 1, 2, 3, 4) sincetargetis 4. We havef = [1, 0, 0, 0, 0]. -
Considering the first die: We create a temporary array
gwhich will be used to compute the sums reachable with one die. Forj = 1totarget(which is 4 in this example), we calculate the number of ways to reach the sumjby adding the face values of the die tof[j - h], wherehranges from 1 tomin(j, k).- For
j = 1,g[1] = f[1 - 1] = f[0] = 1(f[0]initialized as 1). - For
j = 2,g[2] = f[2 - 1] = f[1] = 1(since we could roll a 2 on the first die). - For
j = 3,g[3] = f[3 - 1] = f[2] = 1(rolling a 3 on the first die). - For
j = 4, since the maximum face value (k) is 3, we cannot achieve a sum of 4 with one die, sog[4] = 0. After considering the first die,fgets updated tof = g = [1, 1, 1, 1, 0].
- For
-
Considering the second die: We repeat the process with the second die.
- For
j = 1, there's no change as we can't add a positive face value to reach 1 without exceeding it. - For
j = 2,g[2]will now include the number of ways to reach a sum of1from the first die and then roll a1on the second die, which is just reusing previousf[1] = 1. - For
j = 3,g[3]will include the ways to reach sums of2and1from the first die and rolling1or2on the second die, respectively. Thus,g[3] = f[2] + f[1] = 1 + 1 = 2. - For
j = 4, we sum the ways to get3,2, and1with the first die and roll1,2, or3on the second die:g[4] = f[3] + f[2] + f[1] = 1 + 1 + 1 = 3. Now,fis updated tof = g = [1, 1, 1, 2, 3].
- For
-
Return the answer: After considering all
ndice, in this case, two dice, the final computation for each sum is done. The final answer isf[target], which isf[4]in this case, so there are 3 different ways to roll the dice to get the sum of 4.
By using this approach, we have efficiently computed the desired sum without needing a two-dimensional array, thus optimizing our space usage. For larger values of n and k, following the same steps while considering the modulo 10^9 + 7 would ensure we avoid integer overflow issues.
Solution Implementation
1class Solution:
2 def numRollsToTarget(self, dice: int, sides: int, target: int) -> int:
3 # Initialize the array of ways to achieve each sum, with 1 way to achieve a sum of 0
4 ways_to_achieve_sum = [1] + [0] * target
5 # Define the modulo according to the problem statement to avoid large numbers
6 modulo = 10**9 + 7
7
8 # Iterate through each dice
9 for i in range(1, dice + 1):
10 # Initialize the temporary array for the current dice's sum calculations
11 current_ways = [0] * (target + 1)
12 # Calculate the number of ways to achieve each sum with the current number of dice
13 for sum_value in range(1, min(i * sides, target) + 1):
14 # Calculate the ways to get to this sum_value using the previous number of dice
15 for face_value in range(1, min(sum_value, sides) + 1):
16 current_ways[sum_value] = (current_ways[sum_value] + ways_to_achieve_sum[sum_value - face_value]) % modulo
17 # Update the array of ways with the current dice's calculation
18 ways_to_achieve_sum = current_ways
19
20 # Return the total number of ways to achieve the target sum with all dice
21 return ways_to_achieve_sum[target]
221class Solution {
2 public int numRollsToTarget(int n, int k, int target) {
3 final int MODULO = (int) 1e9 + 7; // Define the modulo to prevent integer overflow
4 int[] dp = new int[target + 1]; // dp array to store the number of ways to achieve each sum
5 dp[0] = 1; // Base case: there's 1 way to achieve sum 0 - no dice rolled
6
7 // Loop through each dice
8 for (int diceCount = 1; diceCount <= n; ++diceCount) {
9 int[] tempDp = new int[target + 1]; // Temporary array for the current number of dices
10
11 // Calculate number of ways for each sum value possible with the current number of dices
12 for (int currentSum = 1; currentSum <= Math.min(target, diceCount * k); ++currentSum) {
13
14 // Go through each face value of the dice and accumulate ways to achieve 'currentSum'
15 for (int faceValue = 1; faceValue <= Math.min(currentSum, k); ++faceValue) {
16 tempDp[currentSum] = (tempDp[currentSum] + dp[currentSum - faceValue]) % MODULO;
17 }
18 }
19
20 // Update the dp array with the current number of dices' results
21 dp = tempDp;
22 }
23
24 // Return the number of ways to achieve the 'target' sum with 'n' dices
25 return dp[target];
26 }
27}
281class Solution {
2public:
3 // Function to calculate the number of distinct ways to roll the dice
4 // such that the sum of the face-up numbers equals to 'target'
5 int numRollsToTarget(int numberOfDice, int faces, int targetSum) {
6 const int MODULO = 1e9 + 7; // Modulo for avoiding integer overflow
7
8 // Create a dynamic programming table initialized with zeros,
9 // `dp[currentTarget]` will represent the number of ways to get sum `currentTarget`
10 vector<int> dp(targetSum + 1, 0);
11
12 // Base case: one way to reach sum 0 - by not choosing any dice
13 dp[0] = 1;
14
15 // Iterate over the number of dice
16 for (int i = 1; i <= numberOfDice; ++i) {
17 // Temporary vector to store ways to reach a certain sum with the current dice
18 vector<int> newDp(targetSum + 1, 0);
19
20 // Calculate number of ways to get each sum from 1 to `targetSum` with `i` dice
21 for (int currentSum = 1; currentSum <= min(targetSum, i * faces); ++currentSum) {
22 // Look back at most `faces` steps to find the number of ways to
23 // reach the current sum from previous sums using different face values
24 for (int faceValue = 1; faceValue <= min(currentSum, faces); ++faceValue) {
25 newDp[currentSum] = (newDp[currentSum] + dp[currentSum - faceValue]) % MODULO;
26 }
27 }
28
29 // Move the updated values in `newDp` to `dp` for the next iteration
30 dp = move(newDp);
31 }
32
33 // Final answer is the number of ways to reach `targetSum` with `numberOfDice` dice
34 return dp[targetSum];
35 }
36};
371function numRollsToTarget(diceCount: number, facesPerDie: number, targetSum: number): number {
2 // Initialize a dynamic programming array to keep track of ways to reach each sum
3 const waysToTarget = Array(targetSum + 1).fill(0);
4 waysToTarget[0] = 1; // There is 1 way to reach the sum 0 (rolling no dice)
5
6 // Define a modulus constant to prevent integer overflow
7 const mod = 1e9 + 7;
8
9 // Iterate over each die
10 for (let currentDie = 1; currentDie <= diceCount; ++currentDie) {
11 // Temporary array to calculate the current number of ways to achieve each sum
12 const tempWays = Array(targetSum + 1).fill(0);
13
14 // Calculate for all possible sums up to the current target
15 // constrained by the number of dice thrown so far and the desired target
16 for (let currentTarget = 1; currentTarget <= Math.min(currentDie * facesPerDie, targetSum); ++currentTarget) {
17 // Check for all the possible outcomes of a single die roll and update
18 for (let faceValue = 1; faceValue <= Math.min(currentTarget, facesPerDie); ++faceValue) {
19 // Update the ways to achieve currentTarget sum considering the current die roll
20 tempWays[currentTarget] = (tempWays[currentTarget] + waysToTarget[currentTarget - faceValue]) % mod;
21 }
22 }
23
24 // Update the original waysToTarget array with the computed values for the current die roll
25 waysToTarget.splice(0, targetSum + 1, ...tempWays);
26 }
27
28 // Return the number of ways to reach the desired target sum using all the dice
29 return waysToTarget[targetSum];
30}
31Which two pointer techniques do you use to check if a string is a palindrome?
Time and Space Complexity
The given Python code is solving the problem of finding the number of distinct ways to roll a set of dice so that the sum of the faces equals the target sum.
Time Complexity:
The time complexity of the code can be analyzed based on the nested loops present in the function:
- There is an outer loop running
niterations wherenis the number of dice. - The first inner loop iterates up to
min(i * k, target). Sinceigoes from1ton, in the worst case, this loop runstargettimes. - The second inner loop iterates up to
min(j, k). In the worst case,jcan betarget, this loop runsktimes.
In the worst case, the time complexity of the algorithm will be O(n * target * k).
Space Complexity:
Based on the reference answer and the code provided, we are using a rolling array (f) to represent the states, which has a size of target + 1.
fandgarrays both are of sizetarget + 1, but they are reused in every iteration instead of creating a 2D array of sizen * target.
Hence, the space complexity of the algorithm is O(target), as only a single-dimensional array is used which is proportional to the target value.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___ in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
121public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
161function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.