Probability that the sum of all numbers obtained on throwing a dice N times lies between two given integers
Given three integers N, A, and B, the task is to calculate the probability that the sum of numbers obtained on throwing the dice exactly N times lies between A and B.
Examples:
Input: N = 1, A = 2, B = 3
Output: 0.333333
Explanation: Ways to obtained the sum 2 by N ( = 1) throws of a dice is 1 {2}. Therefore, required probability = 1/6 = 0.33333Input: N = 2, A = 3, B = 4
Output: 0.138889
Recursive Approach: Follow the steps below to solve the problem:
- Calculate probabilities for all the numbers between A and B and add them to get the answer.
- Call function find(N, sum) to calculate the probability for each number from a to b, where a number between a and b will be passed as sum.
- Base cases are:
- If the sum is either greater than 6 * N or less than N, then return 0 as it’s impossible to have sum greater than N * 6 or less than N.
- If N is equal to 1 and sum is in between 1 and 6, then return 1/6.
- Since at every state any number out of 1 to 6 in a single throw of dice may come, therefore recursion call should be made for the (sum up to that state – i) where 1≤ i ≤ 6.
- Return the resultant probability.
- Base cases are:
Recursion call:
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the // probability for the given // sum to be equal to sum in // N throws of dice long double find( int N, int sum) { // Base cases if (sum > 6 * N || sum < N) return 0; if (N == 1) { if (sum >= 1 && sum <= 6) return 1.0 / 6; else return 0; } long double s = 0; for ( int i = 1; i <= 6; i++) s = s + find(N - 1, sum - i) / 6; return s; } // Driver Code int main() { int N = 4, a = 13, b = 17; long double probability = 0.0; for ( int sum = a; sum <= b; sum++) probability = probability + find(N, sum); // Print the answer cout << fixed << setprecision(6) << probability; return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to calculate the // probability for the given // sum to be equal to sum in // N throws of dice static double find( int N, int sum) { // Base cases if (sum > 6 * N || sum < N) return 0 ; if (N == 1 ) { if (sum >= 1 && sum <= 6 ) return 1.0 / 6 ; else return 0 ; } double s = 0 ; for ( int i = 1 ; i <= 6 ; i++) s = s + find(N - 1 , sum - i) / 6 ; return s; } // Driver code public static void main(String[] args) { int N = 4 , a = 13 , b = 17 ; double probability = 0.0 ; for ( int sum = a; sum <= b; sum++) probability = probability + find(N, sum); // Print the answer System.out.format( "%.6f" , probability); } } // This code is contributed by code_hunt. |
Python3
# Python 2 program for above approach # Function to calculate the # probability for the given # sum to be equal to sum in # N throws of dice def find(N, sum ): # Base cases if ( sum > 6 * N or sum < N): return 0 if (N = = 1 ): if ( sum > = 1 and sum < = 6 ): return 1.0 / 6 else : return 0 s = 0 for i in range ( 1 , 7 ): s = s + find(N - 1 , sum - i) / 6 return s # Driver Code if __name__ = = "__main__" : N = 4 a = 13 b = 17 probability = 0.0 for sum in range (a, b + 1 ): probability = probability + find(N, sum ) # Print the answer print ( round (probability, 6 )) # This code is contributed by chitranayal. |
C#
// C# program for the above approach using System; class GFG { // Function to calculate the // probability for the given // sum to be equal to sum in // N throws of dice static double find( int N, int sum) { // Base cases if (sum > 6 * N || sum < N) return 0; if (N == 1) { if (sum >= 1 && sum <= 6) return 1.0 / 6; else return 0; } double s = 0; for ( int i = 1; i <= 6; i++) s = s + find(N - 1, sum - i) / 6; return s; } // Driver code static void Main() { int N = 4, a = 13, b = 17; double probability = 0.0; for ( int sum = a; sum <= b; sum++) probability = probability + find(N, sum); // Print the answer Console.WriteLine(Math.Round(probability,6)); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript program for the above approach // Function to calculate the // probability for the given // sum to be equal to sum in // N throws of dice function find(N, sum) { // Base cases if (sum > 6 * N || sum < N) return 0; if (N == 1) { if (sum >= 1 && sum <= 6) return 1.0 / 6; else return 0; } let s = 0; for (let i = 1; i <= 6; i++) s = s + find(N - 1, sum - i) / 6; return s; } let N = 4, a = 13, b = 17; let probability = 0.0; for (let sum = a; sum <= b; sum++) probability = probability + find(N, sum); // Print the answer document.write(probability.toFixed(6)); </script> |
Output:
0.505401
Time Complexity: O((b-a+1)6n)
Auxiliary Space: O(1)
Dynamic Programming Approach: The above recursive approach needs to be optimized by dealing with the following overlapping subproblems and optimal substructure:
Overlapping Subproblems:
Partial recursion tree for N=4 and sum=15:
Optimal Substructure:
For every state, recur for other 6 states, so the recursive definition of f(N, sum) is:
Top-Down Approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; float dp[105][605]; // Function to calculate the // probability for the given // sum to be equal to sum in // N throws of dice float find( int N, int sum) { if (dp[N][sum]) return dp[N][sum]; // Base cases if (sum > 6 * N || sum < N) return 0; if (N == 1) { if (sum >= 1 && sum <= 6) return 1.0 / 6; else return 0; } for ( int i = 1; i <= 6; i++) dp[N][sum] = dp[N][sum] + find(N - 1, sum - i) / 6; return dp[N][sum]; } // Driver Code int main() { int N = 4, a = 13, b = 17; float probability = 0.0; // Calculate probability of all // sums from a to b for ( int sum = a; sum <= b; sum++) probability = probability + find(N, sum); // Print the answer cout << fixed << setprecision(6) << probability; return 0; } |
Java
// Java program for above approach class GFG { static float [][] dp = new float [ 105 ][ 605 ]; // Function to calculate the // probability for the given // sum to be equal to sum in // N throws of dice static float find( int N, int sum) { if (N < 0 | sum < 0 ) return 0 ; if (dp[N][sum] > 0 ) return dp[N][sum]; // Base cases if (sum > 6 * N || sum < N) return 0 ; if (N == 1 ) { if (sum >= 1 && sum <= 6 ) return ( float ) ( 1.0 / 6 ); else return 0 ; } for ( int i = 1 ; i <= 6 ; i++) dp[N][sum] = dp[N][sum] + find(N - 1 , sum - i) / 6 ; return dp[N][sum]; } // Driver Code public static void main(String[] args) { int N = 4 , a = 13 , b = 17 ; float probability = 0 .0f; // Calculate probability of all // sums from a to b for ( int sum = a; sum <= b; sum++) probability = probability + find(N, sum); // Print the answer System.out.printf( "%.6f" , probability); } } // This code is contributed by shikhasingrajput |
Python3
# Python program for above approach dp = [[ 0 for i in range ( 605 )] for j in range ( 105 )]; # Function to calculate the # probability for the given # sum to be equal to sum in # N throws of dice def find(N, sum ): if (N < 0 | sum < 0 ): return 0 ; if (dp[N][ sum ] > 0 ): return dp[N][ sum ]; # Base cases if ( sum > 6 * N or sum < N): return 0 ; if (N = = 1 ): if ( sum > = 1 and sum < = 6 ): return ( float )( 1.0 / 6 ); else : return 0 ; for i in range ( 1 , 7 ): dp[N][ sum ] = dp[N][ sum ] + find(N - 1 , sum - i) / 6 ; return dp[N][ sum ]; # Driver Code if __name__ = = '__main__' : N = 4 ; a = 13 ; b = 17 ; probability = 0.0 f = 0 ; # Calculate probability of all # sums from a to b for sum in range (a,b + 1 ): probability = probability + find(N, sum ); # Print the answer print ( "%.6f" % probability); # This code is contributed by 29AjayKumar |
C#
// C# program for above approach using System; using System.Collections.Generic; public class GFG { static float [,] dp = new float [105, 605]; // Function to calculate the // probability for the given // sum to be equal to sum in // N throws of dice static float find( int N, int sum) { if (N < 0 | sum < 0) return 0; if (dp[N, sum] > 0) return dp[N, sum]; // Base cases if (sum > 6 * N || sum < N) return 0; if (N == 1) { if (sum >= 1 && sum <= 6) return ( float ) (1.0 / 6); else return 0; } for ( int i = 1; i <= 6; i++) dp[N, sum] = dp[N, sum] + find(N - 1, sum - i) / 6; return dp[N, sum]; } // Driver Code public static void Main(String[] args) { int N = 4, a = 13, b = 17; float probability = 0.0f; // Calculate probability of all // sums from a to b for ( int sum = a; sum <= b; sum++) probability = probability + find(N, sum); // Print the answer Console.Write( "{0:F6}" , probability); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for above approach var dp = Array(105).fill().map(()=>Array(605).fill(0.0)); // Function to calculate the // probability for the given // sum to be equal to sum in // N throws of dice function find(N, sum) { if (N < 0 | sum < 0) return 0; if (dp[N][sum] > 0) return dp[N][sum]; // Base cases if (sum > 6 * N || sum < N) return 0; if (N == 1) { if (sum >= 1 && sum <= 6) return (1.0 / 6); else return 0; } for ( var i = 1; i <= 6; i++) dp[N][sum] = dp[N][sum] + find(N - 1, sum - i) / 6; return dp[N][sum]; } // Driver Code var N = 4, a = 13, b = 17; var probability = 0.0; // Calculate probability of all // sums from a to b for (sum = a; sum <= b; sum++) probability = probability + find(N, sum); // Print the answer document.write(probability.toFixed(6)); // This code is contributed by umadevi9616 </script> |
Output:
0.505401
Time Complexity: O(n*sum)
Auxiliary Space: O(n*sum)
Bottom-Up Approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; float dp[105][605]; // Function to calculate probability // that the sum of numbers on N throws // of dice lies between A and B float find( int N, int a, int b) { float probability = 0.0; // Base case for ( int i = 1; i <= 6; i++) dp[1][i] = 1.0 / 6; for ( int i = 2; i <= N; i++) { for ( int j = i; j <= 6 * i; j++) { for ( int k = 1; k <= 6; k++) { dp[i][j] = dp[i][j] + dp[i - 1][j - k] / 6; } } } // Add the probability for all // the numbers between a and b for ( int sum = a; sum <= b; sum++) probability = probability + dp[N][sum]; return probability; } // Driver Code int main() { int N = 4, a = 13, b = 17; float probability = find(N, a, b); // Print the answer cout << fixed << setprecision(6) << probability; return 0; } |
Java
// Java program for above approach import java.util.*; class GFG{ static float [][]dp = new float [ 105 ][ 605 ]; // Function to calculate probability // that the sum of numbers on N throws // of dice lies between A and B static float find( int N, int a, int b) { float probability = 0 .0f; // Base case for ( int i = 1 ; i <= 6 ; i++) dp[ 1 ][i] = ( float ) ( 1.0 / 6 ); for ( int i = 2 ; i <= N; i++) { for ( int j = i; j <= 6 * i; j++) { for ( int k = 1 ; k <= 6 && k <= j; k++) { dp[i][j] = dp[i][j] + dp[i - 1 ][j - k] / 6 ; } } } // Add the probability for all // the numbers between a and b for ( int sum = a; sum <= b; sum++) probability = probability + dp[N][sum]; return probability; } // Driver Code public static void main(String[] args) { int N = 4 , a = 13 , b = 17 ; float probability = find(N, a, b); // Print the answer System.out.printf( "%.6f" ,probability); } } // This codeis contributed by shikhasingrajput |
Python3
# Python3 program for above approach dp = [[ 0 for i in range ( 605 )] for j in range ( 105 )] # Function to calculate probability # that the sum of numbers on N throws # of dice lies between A and B def find(N, a, b) : probability = 0.0 # Base case for i in range ( 1 , 7 ) : dp[ 1 ][i] = 1.0 / 6 for i in range ( 2 , N + 1 ) : for j in range (i, ( 6 * i) + 1 ) : for k in range ( 1 , 7 ) : dp[i][j] = dp[i][j] + dp[i - 1 ][j - k] / 6 # Add the probability for all # the numbers between a and b for Sum in range (a, b + 1 ) : probability = probability + dp[N][ Sum ] return probability N, a, b = 4 , 13 , 17 probability = find(N, a, b) # Print the answer print ( '%.6f' % probability) # This code is contributed by divyesh072019. |
C#
// C# program for above approach using System; public class GFG { static float [,]dp = new float [105, 605]; // Function to calculate probability // that the sum of numbers on N throws // of dice lies between A and B static float find( int N, int a, int b) { float probability = 0.0f; // Base case for ( int i = 1; i <= 6; i++) dp[1, i] = ( float ) (1.0 / 6); for ( int i = 2; i <= N; i++) { for ( int j = i; j <= 6 * i; j++) { for ( int k = 1; k <= 6 && k <= j; k++) { dp[i, j] = dp[i, j] + dp[i - 1, j - k] / 6; } } } // Add the probability for all // the numbers between a and b for ( int sum = a; sum <= b; sum++) probability = probability + dp[N, sum]; return probability; } // Driver Code public static void Main(String[] args) { int N = 4, a = 13, b = 17; float probability = find(N, a, b); // Print the answer Console.Write( "{0:F6}" ,probability); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program of the above approach let dp = new Array(105); // Loop to create 2D array using 1D array for ( var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } for ( var i = 0; i < dp.length; i++) { for ( var j = 0; j < dp.length; j++) { dp[i][j] = 0; } } // Function to calculate probability // that the sum of numbers on N throws // of dice lies between A and B function find(N, a, b) { let probability = 0.0; // Base case for (let i = 1; i <= 6; i++) dp[1][i] = (1.0 / 6); for (let i = 2; i <= N; i++) { for (let j = i; j <= 6 * i; j++) { for (let k = 1; k <= 6 && k <= j; k++) { dp[i][j] = dp[i][j] + dp[i - 1][j - k] / 6; } } } // Add the probability for all // the numbers between a and b for (let sum = a; sum <= b; sum++) probability = probability + dp[N][sum]; return probability; } // Driver Code let N = 4, a = 13, b = 17; let probability = find(N, a, b); // Print the answer document.write(probability); // This code is contributed by chinmoy1997pal </script> |
Output:
0.505401
Time Complexity: O(N * sum)
Auxiliary Space: O(N * sum)
Contact Us