101 Logo
onenoughtone

Code Implementation

Number of Dice Rolls With Target Sum Implementation

Below is the implementation of the number of dice rolls with target sum:

solution.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/**
 * Calculate the number of possible ways to roll the dice so the sum equals target.
 * Dynamic Programming (2D) approach.
 *
 * @param {number} n - Number of dice
 * @param {number} k - Number of faces on each die
 * @param {number} target - Target sum
 * @return {number} - Number of possible ways
 */
function numRollsToTarget(n, k, target) {
  const MOD = 1000000007;
 
  // Initialize DP array
  // dp[i][j] = number of ways to achieve sum j using i dice
  const dp = Array(n + 1).fill().map(() => Array(target + 1).fill(0));
 
  // Base case: there is one way to achieve sum 0 with 0 dice
  dp[0][0] = 1;
 
  // Fill DP array
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= target; j++) {
      // Consider all possible values of the current die
      for (let face = 1; face <= k; face++) {
        if (j - face >= 0) {
          dp[i][j] = (dp[i][j] + dp[i - 1][j - face]) % MOD;
        }
      }
    }
  }
 
  return dp[n][target];
}
 
/**
 * Calculate the number of possible ways to roll the dice so the sum equals target.
 * Dynamic Programming (1D) approach.
 *
 * @param {number} n - Number of dice
 * @param {number} k - Number of faces on each die
 * @param {number} target - Target sum
 * @return {number} - Number of possible ways
 */
function numRollsToTargetOptimized(n, k, target) {
  const MOD = 1000000007;
 
  // Initialize arrays for previous and current dice
  let prev = Array(target + 1).fill(0);
  let curr = Array(target + 1).fill(0);
 
  // Base case: there is one way to achieve sum 0 with 0 dice
  prev[0] = 1;
 
  // Fill arrays
  for (let i = 1; i <= n; i++) {
    // Reset curr array
    curr = Array(target + 1).fill(0);
 
    for (let j = 1; j <= target; j++) {
      // Consider all possible values of the current die
      for (let face = 1; face <= k; face++) {
        if (j - face >= 0) {
          curr[j] = (curr[j] + prev[j - face]) % MOD;
        }
      }
    }
 
    // Update prev array
    prev = [...curr];
  }
 
  return prev[target];
}
 
/**
 * Calculate the number of possible ways to roll the dice so the sum equals target.
 * Dynamic Programming with further space optimization.
 *
 * @param {number} n - Number of dice
 * @param {number} k - Number of faces on each die
 * @param {number} target - Target sum
 * @return {number} - Number of possible ways
 */
function numRollsToTargetMoreOptimized(n, k, target) {
  const MOD = 1000000007;
 
  // Early return for impossible cases
  if (target < n || target > n * k) {
    return 0;
  }
 
  // Initialize array for DP
  let dp = Array(target + 1).fill(0);
 
  // Base case: there is one way to achieve sum 0 with 0 dice
  dp[0] = 1;
 
  // Fill DP array
  for (let i = 1; i <= n; i++) {
    // Create a new array for the current iteration
    const newDp = Array(target + 1).fill(0);
 
    for (let j = i; j <= Math.min(i * k, target); j++) {
      // Consider all possible values of the current die
      for (let face = 1; face <= k; face++) {
        if (j - face >= 0) {
          newDp[j] = (newDp[j] + dp[j - face]) % MOD;
        }
      }
    }
 
    // Update dp array
    dp = newDp;
  }
 
  return dp[target];
}
 
// Test cases
console.log(numRollsToTarget(1, 6, 3));  // 1
console.log(numRollsToTarget(2, 6, 7));  // 6
console.log(numRollsToTarget(30, 30, 500));  // 222616187
 
console.log(numRollsToTargetOptimized(1, 6, 3));  // 1
console.log(numRollsToTargetOptimized(2, 6, 7));  // 6
console.log(numRollsToTargetOptimized(30, 30, 500));  // 222616187
 
console.log(numRollsToTargetMoreOptimized(1, 6, 3));  // 1
console.log(numRollsToTargetMoreOptimized(2, 6, 7));  // 6
console.log(numRollsToTargetMoreOptimized(30, 30, 500));  // 222616187

Step-by-Step Explanation

Let's break down the implementation:

  1. Initialize DP Array: Set up a dynamic programming array to keep track of the number of ways to achieve each sum using each number of dice.
  2. Establish Base Case: Define the base case: there is one way to achieve a sum of 0 using 0 dice (by not rolling any die).
  3. Fill DP Array: For each number of dice and each possible sum, consider all possible values of the current die and update the DP array accordingly.
  4. Apply Modulo Operation: Apply the modulo operation at each step to avoid integer overflow, as the answer can be very large.
  5. Return Final Answer: Return the number of ways to achieve the target sum using all n dice, which is stored in dp[n][target].
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone