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 
. Our task is to calculate the expected maximum number of dots after tossing the dice 
times.
Examples:
Input: 2 2
Output: 1.750000000000
Here the dice includes {1, 2}.
So, the sample space of throwing the dice two times =
{(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.750000000000Input: 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 
.
Take m = 6, n = 2 as an instance.
Total numbers with a maximum =6 are equal to 
.
The total numbers with a maximum, 5 are equal to 
.
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 
may cause overflow, so we could move the divisor into the sum and calculate 
instead.
C++
// CPP program for above implementation#include <bits/stdc++.h>using namespace std;// Function find the maximum expectationdouble 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 codeint main(){ double m = 6, n = 3; cout << expect(m, n); return 0;} |
Java
// Java program for above implementationclass GFG{// Function find the maximum expectationstatic 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 codepublic 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 # expectationdef 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 codeif __name__ == "__main__" : # multiple assignments m,n = 6,3 # function calling print(expect(m,n)) |
C#
// C# program for above implementationusing System;class GFG{// Function find the maximum expectationstatic 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 codepublic 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 expectationfunction 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> |
4.95833
Time Complexity: O(m * log n), where m and n are given inputs.
Auxiliary Space: O(1), as constant space is used.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
