Given n dices, each with m faces, numbered from 1 to m, find the number of ways to get a given sum X. X is the summation of values on each face when all the dice are thrown.
Examples:
Input : faces = 4 throws = 2 sum =4
Output : 3
Ways to reach sum equal to 4 in 2 throws can be { (1, 3), (2, 2), (3, 1) }
Input : faces = 6 throws = 3 sum = 12
Output : 25
Approach:
Basically, it is asked to achieve sum in n number of operations using the values in the range [1…m].
Use dynamic programming top-down methodology for this problem. The steps are:
- Base Cases:
- If (sum == 0 and noofthrowsleft ==0) return 1 . It means that sum x has
been achieved. - If (sum < 0 and noofthrowsleft ==0) return 0.It means that sum x has not
been achieved in all throws.
- If (sum == 0 and noofthrowsleft ==0) return 1 . It means that sum x has
- If present sum with present noofthrowsleft is already achieved then return it from the table instead of re computation.
- Then we will loop through all the values of faces from i=[1..m] and recursively moving to achieve sum-i and also decrease the noofthrowsleft by 1.
- Finally, we will store current values in the dp array
Below is the implementation of the above method:
C++
// C++ function to calculate the number of// ways to achieve sum x in n no of throws#include <bits/stdc++.h>using namespace std;#define mod 1000000007int dp[55][55];// Function to calculate recursively the// number of ways to get sum in given// throws and [1..m] valuesint NoofWays(int face, int throws, int sum){ // Base condition 1 if (sum == 0 && throws == 0) return 1; // Base condition 2 if (sum < 0 || throws == 0) return 0; // If value already calculated donot // move into re-computation if (dp[throws][sum] != -1) return dp[throws][sum]; int ans = 0; for (int i = 1; i <= face; i++) { // Recursively moving for sum-i in // throws-1 no of throws left ans += NoofWays(face, throws - 1, sum - i); } // Inserting present values in dp return dp[throws][sum] = ans;}// Driver functionint main(){ int faces = 6, throws = 3, sum = 12; memset(dp, -1, sizeof dp); cout << NoofWays(faces, throws, sum) << endl; return 0;} |
Java
// Java function to calculate the number of // ways to achieve sum x in n no of throwsVal class GFG { static int mod = 1000000007; static int[][] dp = new int[55][55]; // Function to calculate recursively the // number of ways to get sum in given // throwsVal and [1..m] values static int NoofWays(int face, int throwsVal, int sum) { // Base condition 1 if (sum == 0 && throwsVal == 0) { return 1; } // Base condition 2 if (sum < 0 || throwsVal == 0) { return 0; } // If value already calculated donot // move into re-computation if (dp[throwsVal][sum] != -1) { return dp[throwsVal][sum]; } int ans = 0; for (int i = 1; i <= face; i++) { // Recursively moving for sum-i in // throwsVal-1 no of throwsVal left ans += NoofWays(face, throwsVal - 1, sum - i); } // Inserting present values in dp return dp[throwsVal][sum] = ans; } // Driver code public static void main(String[] args) { int faces = 6, throwsVal = 3, sum = 12; for (int i = 0; i < 55; i++) { for (int j = 0; j < 55; j++) { dp[i][j] = -1; } } System.out.println(NoofWays(faces, throwsVal, sum)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 function to calculate the number of # ways to achieve sum x in n no of throws import numpy as npmod = 1000000007;dp = np.zeros((55,55)); # Function to calculate recursively the # number of ways to get sum in given # throws and [1..m] values def NoofWays(face, throws, sum) : # Base condition 1 if (sum == 0 and throws == 0) : return 1; # Base condition 2 if (sum < 0 or throws == 0) : return 0; # If value already calculated donot # move into re-computation if (dp[throws][sum] != -1) : return dp[throws][sum]; ans = 0; for i in range(1, face + 1) : # Recursively moving for sum-i in # throws-1 no of throws left ans += NoofWays(face, throws - 1, sum - i); # Inserting present values in dp dp[throws][sum] = ans; return ans;# Driver function if __name__ == "__main__" : faces = 6; throws = 3; sum = 12; for i in range(55) : for j in range(55) : dp[i][j] = -1 print(NoofWays(faces, throws, sum)) ; # This code is contributed by AnkitRai01 |
C#
// C# function to calculate the number of // ways to achieve sum x in n no of throwsVal using System;class GFG{ static int[,]dp = new int[55,55]; // Function to calculate recursively the // number of ways to get sum in given // throwsVal and [1..m] values static int NoofWays(int face, int throwsVal, int sum) { // Base condition 1 if (sum == 0 && throwsVal == 0) { return 1; } // Base condition 2 if (sum < 0 || throwsVal == 0) { return 0; } // If value already calculated donot // move into re-computation if (dp[throwsVal,sum] != -1) { return dp[throwsVal,sum]; } int ans = 0; for (int i = 1; i <= face; i++) { // Recursively moving for sum-i in // throwsVal-1 no of throwsVal left ans += NoofWays(face, throwsVal - 1, sum - i); } // Inserting present values in dp return dp[throwsVal,sum] = ans; } // Driver code static public void Main () { int faces = 6, throwsVal = 3, sum = 12; for (int i = 0; i < 55; i++) { for (int j = 0; j < 55; j++) { dp[i,j] = -1; } } Console.WriteLine(NoofWays(faces, throwsVal, sum)); }}// This code is contributed by ajit. |
Javascript
<script>// Javascript function to calculate the number of// ways to achieve sum x in n no of throwsconst mod = 1000000007;let dp = new Array(55);for (let i = 0; i < 55; i++) dp[i] = new Array(55).fill(-1);// Function to calculate recursively the// number of ways to get sum in given// throws and [1..m] valuesfunction NoofWays(face, throws, sum){ // Base condition 1 if (sum == 0 && throws == 0) return 1; // Base condition 2 if (sum < 0 || throws == 0) return 0; // If value already calculated donot // move into re-computation if (dp[throws][sum] != -1) return dp[throws][sum]; let ans = 0; for (let i = 1; i <= face; i++) { // Recursively moving for sum-i in // throws-1 no of throws left ans += NoofWays(face, throws - 1, sum - i); } // Inserting present values in dp return dp[throws][sum] = ans;}// Driver function let faces = 6, throws = 3, sum = 12; document.write(NoofWays(faces, throws, sum));</script> |
Output:
25
Time complexity : O(throws*faces*sum)
Space complexity : O(faces*sum)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a 2D array DP to store the solution of the subproblems and initialize it with 0.
- Initialize the DP with base cases.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- Return the final solution stored in dp[throws][sum] .
Implementation :
C++
// c++ code above approach#include <bits/stdc++.h>using namespace std;#define mod 1000000007int dp[55][55];// Function to calculate recursively the// number of ways to get sum in given// throws and [1..m] valuesint NoofWays(int face, int throws, int sum){ memset(dp, 0, sizeof dp); // Initialize base conditions for (int i = 1; i <= face && i <= sum; i++) dp[1][i] = 1; // iterate over subproblems to get the current solution for (int t = 2; t <= throws; t++) { for (int s = 1; s <= sum; s++) { for (int i = 1; i <= face && i < s; i++) { // get current value from previous computations dp[t][s] += dp[t - 1][s - i]; dp[t][s] %= mod; } } } // return answer return dp[throws][sum];} // Driver codeint main(){ int faces = 6, throws = 3, sum = 12; // function call cout << NoofWays(faces, throws, sum) << endl; return 0;} |
Java
import java.util.*;public class Main { static int mod = 1000000007; static int[][] dp = new int[55][55]; // Function to calculate recursively the // number of ways to get sum in given // throws and [1..m] values static int NoofWays(int face, int throws_, int sum) { Arrays.stream(dp).forEach(a -> Arrays.fill(a, 0)); // Initialize base conditions for (int i = 1; i <= face && i <= sum; i++) dp[1][i] = 1; // iterate over subproblems to get the current // solution for (int t = 2; t <= throws_; t++) { for (int s = 1; s <= sum; s++) { for (int i = 1; i <= face && i < s; i++) { // get current value from previous // computations dp[t][s] += dp[t - 1][s - i]; dp[t][s] %= mod; } } } // return answer return dp[throws_][sum]; } // Driver code public static void main(String[] args) { int faces = 6, throws_ = 3, sum = 12; // function call System.out.println(NoofWays(faces, throws_, sum)); }} |
Python3
mod = 1000000007# Function to calculate recursively the# number of ways to get sum in given# throws and [1..m] valuesdef NoofWays(face, throws, sum): dp = [[0 for i in range(sum + 1)] for j in range(throws + 1)] # Initialize base conditions for i in range(1, face + 1): if i <= sum: dp[1][i] = 1 # iterate over subproblems to get the current solution for t in range(2, throws + 1): for s in range(1, sum + 1): for i in range(1, face + 1): if i < s: # get current value from previous computations dp[t][s] += dp[t - 1][s - i] dp[t][s] %= mod # return answer return dp[throws][sum]faces = 6throws = 3sum = 12# function callprint(NoofWays(faces, throws, sum)) |
C#
// C# code for above approachusing System;class MainClass { // Function to calculate recursively the // number of ways to get sum in given // throws and [1..m] values public static int NoofWays(int face, int throws, int sum) { int[, ] dp = new int[55, 55]; // Initialize base conditions for (int i = 1; i <= face && i <= sum; i++) dp[1, i] = 1; // iterate over subproblems to // get the current solution for (int t = 2; t <= throws; t++) { for (int s = 1; s <= sum; s++) { for (int i = 1; i <= face && i < s; i++) { // Get current value from // previous computations dp[t, s] += dp[t - 1, s - i]; dp[t, s] %= 1000000007; } } } // return answer return dp[throws, sum]; } // Driver code public static void Main(string[] args) { int faces = 6, throws = 3, sum = 12; Console.WriteLine(NoofWays(faces, throws, sum)); }} |
Javascript
// JavaScript code for the approachfunction NoofWays(face, throws, sum) { const mod = 1000000007; const dp = new Array(55).fill().map(() => new Array(55).fill(0)); // Initialize base conditions for (let i = 1; i <= face && i <= sum; i++) { dp[1][i] = 1; } // iterate over subproblems to get the current solution for (let t = 2; t <= throws; t++) { for (let s = 1; s <= sum; s++) { for (let i = 1; i <= face && i < s; i++) { // get current value from previous computations dp[t][s] += dp[t - 1][s - i]; dp[t][s] %= mod; } } } // return answer return dp[throws][sum];}// Driver codeconst faces = 6;const throws = 3;const sum = 12;// function callconsole.log(NoofWays(faces, throws, sum));// This code is contributed by user_dtewbxkn77n |
Output
25
Time complexity : O(throws*faces*sum)
Auxiliary Space : O(throws*sum)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
