Given an integer N, the task is to find the number of ways to get the sum N by repeatedly throwing a dice.
Examples:
Input: N = 3
Output: 4
Explanation:
The four possible ways to obtain N are:
- 1 + 1 + 1
- 1 + 2
- 2 + 1
- 3
Input: N = 2
Output: 2
Explanation:
The two possible ways to obtain N are:
- 1 + 1
- 2
Recursive Approach: The idea is to iterate for every possible value of dice to get the required sum N. Below are the steps:
- Let findWays() be the required answer for sum N.
- The only numbers obtained from the throw of dice are [1, 6], each having equal probability in a single throw of dice.
- Therefore, for every state, recur for the previous (N – i) states (where 1 ? i ? 6). Therefore, the recursive relation is as follows:
findWays(N) = findWays(N – 1) + findWays(N – 2) + findWays(N – 3) + findWays(N – 4) + findWays(N – 5) + findWays(N – 6)
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of ways// to get the sum N with throw of diceint findWays(int N){ // Base Case if (N == 0) { return 1; } // Stores the count of total // number of ways to get sum N int cnt = 0; // Recur for all 6 states for (int i = 1; i <= 6; i++) { if (N - i >= 0) { cnt = cnt + findWays(N - i); } } // Return answer return cnt;}// Driver Codeint main(){ int N = 4; // Function call cout << findWays(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the number of ways// to get the sum N with throw of dicestatic int findWays(int N){ // Base Case if (N == 0) { return 1; } // Stores the count of total // number of ways to get sum N int cnt = 0; // Recur for all 6 states for(int i = 1; i <= 6; i++) { if (N - i >= 0) { cnt = cnt + findWays(N - i); } } // Return answer return cnt;}// Driver Codepublic static void main(String[] args){ int N = 4; // Function call System.out.print(findWays(N));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to find the number of ways# to get the sum N with throw of dicedef findWays(N): # Base case if (N == 0): return 1 # Stores the count of total # number of ways to get sum N cnt = 0 # Recur for all 6 states for i in range(1, 7): if (N - i >= 0): cnt = cnt + findWays(N - i) # Return answer return cnt # Driver Codeif __name__ == '__main__': N = 4 # Function call print(findWays(N))# This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approach using System;class GFG{// Function to find the number of ways// to get the sum N with throw of dicestatic int findWays(int N){ // Base Case if (N == 0) { return 1; } // Stores the count of total // number of ways to get sum N int cnt = 0; // Recur for all 6 states for(int i = 1; i <= 6; i++) { if (N - i >= 0) { cnt = cnt + findWays(N - i); } } // Return answer return cnt;}// Driver Codepublic static void Main(){ int N = 4; // Function call Console.Write(findWays(N));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// JavaScript program for the above approach// Function to find the number of ways// to get the sum N with throw of dicefunction findWays(N){ // Base Case if (N == 0) { return 1; } // Stores the count of total // number of ways to get sum N var cnt = 0; // Recur for all 6 states for (var i = 1; i <= 6; i++) { if (N - i >= 0) { cnt = cnt + findWays(N - i); } } // Return answer return cnt;}// Driver Codevar N = 4;// Function calldocument.write( findWays(N));</script> |
Output:
8
Time Complexity: O(6N)
Auxiliary Space: O(1)
Dynamic Programming Approach: The above recursive approach needs to be optimized by dealing with the following overlapping subproblems:
Overlapping Subproblems:
Partial recursion tree for N = 8:
Optimal Substructure: As for every state, recurrence occurs for 6 states, so the recursive definition of dp(N) is the following:
dp[N] = dp[N-1] + dp[N-2] + dp[N-3] + dp[N-4] + dp[N-5] + dp[N-6]
Follow the steps below to solve the problem:
- Initialize an auxiliary array dp[] of size N + 1 with initial value -1, where dp[i] stores the count of ways of having sum i.
- The base case while solving this problem is if N is equal to 0 in any state, the result to such a state is 1.
- If for any state dp[i] is not equal to -1, then this value as this substructure is already beed calculated.
Top-Down Approach: Below is the implementation of the Top-Down approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the total// number of ways to have sum Nint findWays(int N, int dp[]){ // Base Case if (N == 0) { return 1; } // Return already stored result if (dp[N] != -1) { return dp[N]; } int cnt = 0; // Recur for all 6 states for (int i = 1; i <= 6; i++) { if (N - i >= 0) { cnt = cnt + findWays(N - i, dp); } } // Return the result return dp[N] = cnt;}// Driver Codeint main(){ // Given sum N int N = 4; // Initialize the dp array int dp[N + 1]; memset(dp, -1, sizeof(dp)); // Function Call cout << findWays(N, dp); return 0;} |
Java
// Java Program for // the above approachimport java.util.*;class GFG{// Function to calculate the total// number of ways to have sum Nstatic int findWays(int N, int dp[]){ // Base Case if (N == 0) { return 1; } // Return already // stored result if (dp[N] != -1) { return dp[N]; } int cnt = 0; // Recur for all 6 states for (int i = 1; i <= 6; i++) { if (N - i >= 0) { cnt = cnt + findWays(N - i, dp); } } // Return the result return dp[N] = cnt;}// Driver Codepublic static void main(String[] args){ // Given sum N int N = 4; // Initialize the dp array int []dp = new int[N + 1]; for (int i = 0; i < dp.length; i++) dp[i] = -1; // Function Call System.out.print(findWays(N, dp));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 Program for the # above approach# Function to calculate # the total number of ways # to have sum Ndef findWays(N, dp): # Base Case if (N == 0): return 1 # Return already # stored result if (dp[N] != -1): return dp[N] cnt = 0 # Recur for all 6 states for i in range (1, 7): if (N - i >= 0): cnt = (cnt + findWays(N - i, dp)) # Return the result dp[N] = cnt return dp[N]# Driver Codeif __name__ == "__main__": # Given sum N N = 4 # Initialize the dp array dp = [-1] * (N + 1) # Function Call print(findWays(N, dp))# This code is contributed by Chitranayal |
C#
// C# Program for // the above approachusing System;class GFG{// Function to calculate the total// number of ways to have sum Nstatic int findWays(int N, int []dp){ // Base Case if (N == 0) { return 1; } // Return already stored result if (dp[N] != -1) { return dp[N]; } int cnt = 0; // Recur for all 6 states for (int i = 1; i <= 6; i++) { if (N - i >= 0) { cnt = cnt + findWays(N - i, dp); } } // Return the result return dp[N] = cnt;}// Driver Codepublic static void Main(String[] args){ // Given sum N int N = 4; // Initialize the dp array int []dp = new int[N + 1]; for (int i = 0; i < dp.Length; i++) dp[i] = -1; // Function Call Console.Write(findWays(N, dp));}} // This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript Program for// the above approach// Function to calculate the total// number of ways to have sum Nfunction findWays(N,dp){ // Base Case if (N == 0) { return 1; } // Return already // stored result if (dp[N] != -1) { return dp[N]; } let cnt = 0; // Recur for all 6 states for (let i = 1; i <= 6; i++) { if (N - i >= 0) { cnt = cnt + findWays(N - i, dp); } } // Return the result return dp[N] = cnt;}// Driver Codelet N = 4; // Initialize the dp arraylet dp = new Array(N + 1);for (let i = 0; i < dp.length; i++) dp[i] = -1;// Function Calldocument.write(findWays(N, dp));// This code is contributed by unknown2108</script> |
Output:
8
Time Complexity: O(N)
Auxiliary Space: O(N)
Bottom-Up Approach: Below is the implementation of the Bottom-up Dynamic Programming approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the total// number of ways to have sum Nvoid findWays(int N){ // Initialize dp array int dp[N + 1]; dp[0] = 1; // Iterate over all the possible // intermediate values to reach N for (int i = 1; i <= N; i++) { dp[i] = 0; // Calculate the sum for // all 6 faces for (int j = 1; j <= 6; j++) { if (i - j >= 0) { dp[i] = dp[i] + dp[i - j]; } } } // Print the total number of ways cout << dp[N];}// Driver Codeint main(){ // Given sum N int N = 4; // Function call findWays(N); return 0;} |
Java
// Java program for the above approachimport java.util.*; class GFG{ // Function to calculate the total// number of ways to have sum Nstatic void findWays(int N){ // Initialize dp array int []dp = new int[N + 1]; dp[0] = 1; // Iterate over all the possible // intermediate values to reach N for(int i = 1; i <= N; i++) { dp[i] = 0; // Calculate the sum for // all 6 faces for(int j = 1; j <= 6; j++) { if (i - j >= 0) { dp[i] = dp[i] + dp[i - j]; } } } // Print the total number of ways System.out.print(dp[N]);} // Driver Codepublic static void main(String[] args){ // Given sum N int N = 4; // Function call findWays(N);}} // This code is contributed by Amit Katiyar |
Python3
# Python3 program for # the above approach# Function to calculate the total# number of ways to have sum Ndef findWays(N): # Initialize dp array dp = [0] * (N + 1); dp[0] = 1; # Iterate over all the # possible intermediate # values to reach N for i in range(1, N + 1): dp[i] = 0; # Calculate the sum for # all 6 faces for j in range(1, 7): if (i - j >= 0): dp[i] = dp[i] + dp[i - j]; # Print total number of ways print(dp[N]);# Driver Codeif __name__ == '__main__': # Given sum N N = 4; # Function call findWays(N);# This code is contributed by 29AjayKumar |
C#
// C# program for // the above approachusing System;class GFG{ // Function to calculate the total// number of ways to have sum Nstatic void findWays(int N){ // Initialize dp array int []dp = new int[N + 1]; dp[0] = 1; // Iterate over all the possible // intermediate values to reach N for(int i = 1; i <= N; i++) { dp[i] = 0; // Calculate the sum for // all 6 faces for(int j = 1; j <= 6; j++) { if (i - j >= 0) { dp[i] = dp[i] + dp[i - j]; } } } // Print the total number of ways Console.Write(dp[N]);} // Driver Codepublic static void Main(String[] args){ // Given sum N int N = 4; // Function call findWays(N);}} // This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for the above approach// Function to calculate the total// number of ways to have sum Nfunction findWays(N){ // Initialize dp array let dp = new Array(N + 1); dp[0] = 1; // Iterate over all the possible // intermediate values to reach N for(let i = 1; i <= N; i++) { dp[i] = 0; // Calculate the sum for // all 6 faces for(let j = 1; j <= 6; j++) { if (i - j >= 0) { dp[i] = dp[i] + dp[i - j]; } } } // Print the total number of ways document.write(dp[N]);}// Driver Code // Given sum Nlet N = 4; // Function callfindWays(N);// This code is contributed by patel2127</script> |
Output:
8
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach: space optimization O(1)
To optimize the space complexity of the previous solution by using only an array of size 6 instead of an array of size N+1 to store the values of dp. We only need to store the values for the last 6 values of dp at any point in time.
Implementation Steps:
- Create an array DP if size 6 instead of size N because we need only the previous 6 computations to get the current value.
- Initialize DP with base case dp[0] = 1.
- Iterate over subproblems and get the current value from previous solutions of subproblems stored in DP.
- At the last return, the final answer is stored in dp[N%6]. ( n%6 ) to compute only the last 6 values.
Implementation:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the total// number of ways to have sum Nvoid findWays(int N){ // Initialize dp array int dp[6]; dp[0] = 1; // Iterate over all the possible // intermediate values to reach N for (int i = 1; i <= N; i++) { int sum = 0; // Calculate the sum for // all 6 faces for (int j = 1; j <= 6; j++) { if (i - j >= 0) { sum += dp[(i-j)%6]; } } // Store the sum for the current i dp[i%6] = sum; } // Print the total number of ways cout << dp[N%6];}// Driver Codeint main(){ // Given sum N int N = 4; // Function call findWays(N); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;public class DiceSum { // Function to calculate the total // number of ways to have sum N public static void findWays(int N) { // Initialize dp array int[] dp = new int[6]; dp[0] = 1; // Iterate over all the possible // intermediate values to reach N for (int i = 1; i <= N; i++) { int sum = 0; // Calculate the sum for // all 6 faces for (int j = 1; j <= 6; j++) { if (i - j >= 0) { sum += dp[(i-j)%6]; } } // Store the sum for the current i dp[i%6] = sum; } // Print the total number of ways System.out.println(dp[N%6]); } // Driver Code public static void main(String[] args) { // Given sum N int N = 4; // Function call findWays(N); }} |
Python3
# Python program for above approach# Function to calculate the total# number of ways to have sum Ndef findWays(N): # Initialize dp array dp = [0] * 6 dp[0] = 1 # Iterate over all the possible # intermediate values to reach N for i in range(1, N+1): sum = 0 # Calculate the sum for # all 6 faces for j in range(1, 7): if i - j >= 0: sum += dp[(i-j)%6] # Store the sum for the current i dp[i%6] = sum # Print the total number of ways print(dp[N%6])# Driver Codeif __name__ == '__main__': # Given sum N N = 4 # Function call findWays(N) |
C#
using System;public class MainClass{ public static void Main() { int N = 4; // Initialize dp array int[] dp = new int[6]; dp[0] = 1; // Iterate over all the possible // intermediate values to reach N for (int i = 1; i <= N; i++) { int sum = 0; // Calculate the sum for // all 6 faces for (int j = 1; j <= 6; j++) { if (i - j >= 0) { sum += dp[(i-j)%6]; } } // Store the sum for the current i dp[i%6] = sum; } // Print the total number of ways Console.WriteLine(dp[N%6]); }} |
Javascript
let N = 4;// Initialize dp arraylet dp = new Array(6).fill(0);dp[0] = 1;// Iterate over all the possible// intermediate values to reach Nfor (let i = 1; i <= N; i++) {let sum = 0;// Calculate the sum for// all 6 facesfor (let j = 1; j <= 6; j++) {if (i - j >= 0) {sum += dp[(i - j) % 6];}}// Store the sum for the current idp[i % 6] = sum;}// Print the total number of waysconsole.log(dp[N % 6]); |
Output
8
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
