Maximum number of dots after throwing a dice N times

0 0 4 minutes read

Given a dice with m-faces. The first face of the dice contains a dot, the second one contains two dots, and so on, the m-th face contains m dots. Each face appears with a probability $1/m$ . Our task is to calculate the expected maximum number of dots after tossing the dice $n$ times.

Examples:

Input: 2 2
Output: 1.750000000000
Here the dice includes {1, 2}.
So, the sample space of throwing the dice two times = $2^2$
{(1, 2), (1, 1), (2, 1), (2, 2)}
For (1, 2)–> maximum=2
For (1, 1)–> maximum=1
For (2, 2)–> maximum=2
For (2, 1)–> maximum=2
The probability of each outcome is 0.25,
that is, expectation equals to
(2+1+2+2)*(0.25) = 7/4 = 1.750000000000

Input: 6 3
Output: 4.958333333333

Approach:
The key observation in this problem is that no. of times a number can occur a maximum of times depending upon its previous number.
For i-th number, it will be $i^n-(i-1)^n$ .
Take m = 6, n = 2 as an instance.
Total numbers with a maximum =6 are equal to $6^2-5^2$ .
The total numbers with a maximum, 5 are equal to $5^2-4^2$ .
Similarly, we can find out for 4,3,2, and 1.
6 6 6 6 6 6
5 5 5 5 5 6
4 4 4 4 5 6
3 3 3 4 5 6
2 2 3 4 5 6
1 2 3 4 5 6
Enumerate the maximum number, the distribution will be an n-dimensional super-cube with m-length-side. Each layer will be a large cube minus a smaller cube.
So, our answer will be the sum of all i-th elements from 1 to m given by:

Calculating $i^n$ may cause overflow, so we could move the divisor into the sum and calculate $(i/m)^n$ instead.

C++

// CPP program for above implementation
#include <bits/stdc++.h>
using namespace std;
 
// Function find the maximum expectation
double expect(double m, double n)
{
    double ans = 0.0, i;
 
     
       for (i = m; i; i--)
        // formula to find the maximum number and
        // sum of maximum numbers
        ans += (pow(i / m, n) - pow((i - 1) / m, n)) * i;
   
    return ans;
}
 
// Driver code
int main()
{
    double m = 6, n = 3;
    cout << expect(m, n);
 
 return 0;
}

Java

// Java program for above implementation
class GFG
{
// Function find the maximum expectation
static double expect(double m, double n)
{
    double ans = 0.0, i;
 
    for (i = m; i > 0; i--)
     
        // formula to find the maximum number 
        // and sum of maximum numbers
        ans += (Math.pow(i / m, n) - 
                Math.pow((i - 1) / m, n)) * i;
 
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    double m = 6, n = 3;
    System.out.println(String.format("%.5f",
                             expect(m, n)));
}
}
 
// This code is contributed by mits

Python3

# Python3 program for finding maximum
# number of dots after throwing a 
# dice N times.
 
# Function to find the maximum 
# expectation
def expect(m,n) :
 
    ans = 0.0
    i = m
    while (i):
         
        # formula to find the maximum 
        # number and 
        # sum of maximum numbers 
        ans += (pow(i / m, n) - pow((i-1) / m, n)) * i
        i -= 1
 
    return ans
 
# Driver code
if __name__ == "__main__" :
     
    # multiple assignments
    m,n = 6,3
 
    # function calling
    print(expect(m,n))

C#

// C# program for above implementation
using System;
 
class GFG
{
// Function find the maximum expectation
static double expect(double m, double n)
{
    double ans = 0.0, i;
 
    for (i = m; i > 0; i--)
     
        // formula to find the maximum number 
        // and sum of maximum numbers
        ans += (Math.Pow(i / m, n) - 
                Math.Pow((i - 1) / m, n)) * i;
 
    return ans;
}
 
// Driver code
public static void Main()
{
    double m = 6, n = 3;
    Console.WriteLine(expect(m, n));
}
}
 
// This code is contributed
// by Akanksha Rai

PHP

<?php 
// PHP program for above implementation
 
// Function find the maximum expectation
function expect($m, $n)
{
    $ans = 0.0;
 
    for ($i = $m; $i; $i--)
     
        // formula to find the maximum number 
        // and sum of maximum numbers
        $ans += (pow($i / $m, $n) - 
                 pow(($i - 1) / $m, $n)) * $i;
     
    return $ans;
}
 
// Driver code
$m = 6;
$n = 3;
echo expect($m, $n);
 
// This code is contributed by ChitraNayal
?>

Javascript

<script>
// Javascript program for above implementation
     
    // Function find the maximum expectation
    function expect(m,n)
    {
        let ans = 0.0, i;
   
        for (i = m; i > 0; i--)
       
        // formula to find the maximum number 
        // and sum of maximum numbers
            ans += (Math.pow(i / m, n) - 
                Math.pow((i - 1) / m, n)) * i;
   
        return ans;
    }
     
    // Driver code
    let m = 6, n = 3;
     
    document.write(expect(m, n).toFixed(5))
 
     
 
// This code is contributed by avanitrachhadiya2155
</script>

Output:

4.95833

Time Complexity: O(m * log n), where m and n are given inputs.
Auxiliary Space: O(1), as constant space is used.

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!