Probability of getting all possible values on throwing N dices

0 0 5 minutes read

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.17

Input: 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 code
int 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 dices
import 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 Code
public 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 dices
def 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 code
n = 2
 
# Call the function
diceSum(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 dices
using 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 dices
 
function 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>

Output:

Time Complexity: O(N²)
Auxiliary Space: O(N²)

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 zambiatek!