Given an integer N denoting the number of dices, the task is to find the probability of every possible value that can be obtained by throwing N dices together.
Examples:
Input: N = 1
Output:
1: 0.17
2: 0.17
3: 0.17
4: 0.17
5: 0.17
6: 0.17
Explanation: On throwing a dice, the probability of all values from [1, 6] to appear at the top is 1/6 = 0.17Input: N = 2
Output:
2: 0.028
3: 0.056
4: 0.083
5: 0.11
6: 0.14
7: 0.17
8: 0.14
9: 0.11
10: 0.083
11: 0.056
12: 0.028
Explanation: The possible values of the sum of the two numbers that appear at the top on throwing two dices together ranges between [2, 12].
Approach: The idea is to use Dynamic programming and DP table to store the probability of each possible value.
- Store the probabilities of all the 6 numbers that can appear on throwing 1 dice.
- Now, for N=2, the probability for all possible sums between [2, 12] is equal to the sum of the product of the respective probability of the two numbers that add up to that sum. For example,
Probability of 4 on throwing 2 dices = (Probability of 1 ) * ( Probability of 3) + (Probability of 2) * ( Probability of 2) + (Probability of 3 ) * ( Probability of 1)
- Hence for N dices,
Probability of Sum S = (Probability of 1) * (Probability of S – 1 using N -1 dices) + (Probability of 2) * (Probability of S – 2 using N-1 dices) + ….. + (Probability of 6) * (Probability of S – 6 using N -1 dices)
- Hence, in order to solve the problem, we need to fill dp[][] table from 2 to N using a top-down approach using the relation:
dp[i][x] = dp[1][y] + dp[i-1][z] where x = y + z and i denotes the number of dices
- Display all the probabilities stored for N as the answer.
Below is the implementation of the above approach:
C++
// C++ Program to calculate// the probability of// all the possible values// that can be obtained// throwing N dices#include <bits/stdc++.h>using namespace std;void dicesSum(int n){ // Store the probabilities vector<map<int, double> > dp(n + 1); // Precompute the probabilities // for values possible using 1 dice dp[1] = { { 1, 1 / 6.0 }, { 2, 1 / 6.0 }, { 3, 1 / 6.0 }, { 4, 1 / 6.0 }, { 5, 1 / 6.0 }, { 6, 1 / 6.0 } }; // Compute the probabilities // for all values from 2 to N for (int i = 2; i <= n; i++) { for (auto a1 : dp[i - 1]) { for (auto a2 : dp[1]) { dp[i][a1.first + a2.first] += a1.second * a2.second; } } } // Print the result for (auto a : dp[n]) { cout << a.first << " " << setprecision(2) << a.second << endl; }}// Driver codeint main(){ int n = 2; dicesSum(n); return 0;} |
Java
// Java program to calculate// the probability of all the// possible values that can // be obtained throwing N dicesimport java.io.*;import java.util.*;class GFG{static void dicesSum(int n){ // Store the probabilities double[][] dp = new double[n + 1][6 * n + 1]; // Precompute the probabilities // for values possible using 1 dice for(int i = 1; i <= 6; i++) dp[1][i] = 1 / 6.0; // Compute the probabilities // for all values from 2 to N for(int i = 2; i <= n; i++) for(int j = i - 1; j <= 6 * (i - 1); j++) for(int k = 1; k <= 6; k++) { dp[i][j + k] += (dp[i - 1][j] * dp[1][k]); } // Print the result for(int i = n; i <= 6 * n; i++) { System.out.println(i + " " + Math.round(dp[n][i] * 1000.0) / 1000.0); }}// Driver Codepublic static void main(String[] args){ int n = 2; dicesSum(n);}}// This code is contributed by jithin |
Python3
# Python3 program to calculate# the probability of all the # possible values that can # be obtained throwing N dicesdef diceSum(n): # Initialize a 2d array upto # (n*total sum possible) sum # with value 0 dp = [[ 0 for j in range(n * 6)] for i in range(n + 1)] # Store the probability in a # single throw for 1,2,3,4,5,6 for i in range(6): dp[1][i] = 1 / 6 # Compute the probabilities # for all values from 2 to N for i in range(2, n + 1): for j in range(len(dp[i - 1])): for k in range(6): if (dp[i - 1][j] != 0 and dp[i - 1][k] != 0): dp[i][j + k] += (dp[i - 1][j] * dp[1][k]) # Print the result for i in range(len(dp[n]) - n + 1): print("%d %0.3f" % (i + n, dp[n][i]))# Driver coden = 2# Call the functiondiceSum(n)# This code is contributed by dipesh99kumar |
C#
// C# program to calculate// the probability of all the// possible values that can // be obtained throwing N dicesusing System;class GFG { static void dicesSum(int n) { // Store the probabilities double[,] dp = new double[n + 1,6 * n + 1]; // Precompute the probabilities // for values possible using 1 dice for(int i = 1; i <= 6; i++) dp[1,i] = 1 / 6.0; // Compute the probabilities // for all values from 2 to N for(int i = 2; i <= n; i++) for(int j = i - 1; j <= 6 * (i - 1); j++) for(int k = 1; k <= 6; k++) { dp[i,j + k] += (dp[i - 1,j] * dp[1,k]); } // Print the result for(int i = n; i <= 6 * n; i++) { Console.WriteLine(i + " " + Math.Round(dp[n,i] * 1000.0) / 1000.0); } } static void Main() { int n = 2; dicesSum(n); }}// This code is contributed by divyesh072019 |
Javascript
<script>// JavaScript program to calculate// the probability of all the// possible values that can// be obtained throwing N dicesfunction dicesSum(n){ // Store the probabilities let dp = new Array(n+1); 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 < 6 * n + 1; j++) { dp[i][j] = 0; } } // Precompute the probabilities // for values possible using 1 dice for(let i = 1; i <= 6; i++) dp[1][i] = 1 / 6.0; // Compute the probabilities // for all values from 2 to N for(let i = 2; i <= n; i++) for(let j = i - 1; j <= 6 * (i - 1); j++) for(let k = 1; k <= 6; k++) { dp[i][j + k] += (dp[i - 1][j] * dp[1][k]); } // Print the result for(let i = n; i <= 6 * n; i++) { document.write(i + " " + Math.round(dp[n][i] * 1000.0) / 1000.0 + "<br/>"); }} // Driver Code let n = 2; dicesSum(n); </script> |
2 0.028 3 0.056 4 0.083 5 0.11 6 0.14 7 0.17 8 0.14 9 0.11 10 0.083 11 0.056 12 0.028
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
