Given a linear board of length N numbered from 1 to N, the task is to find the expected number of moves required to reach the Nth cell of the board, if we start at cell numbered 1 and at each step we roll a cubical dice to decide the next move. Also, we cannot go outside the bounds of the board. Note that the expected number of moves can be fractional.
Examples:
Input: N = 8
Output: 7
p1 = (1 / 6) | 1-step -> 6 moves expected to reach the end
p2 = (1 / 6) | 2-steps -> 6 moves expected to reach the end
p3 = (1 / 6) | 3-steps -> 6 moves expected to reach the end
p4 = (1 / 6) | 4-steps -> 6 moves expected to reach the end
p5 = (1 / 6) | 5-steps -> 6 moves expected to reach the end
p6 = (1 / 6) | 6-steps -> 6 moves expected to reach the end
If we are 7 steps away, then we can end up at 1, 2, 3, 4, 5, 6 steps
away with equal probability i.e. (1 / 6).
Look at the above simulation to understand better.
dp[N – 1] = dp[7]
= 1 + (dp[1] + dp[2] + dp[3] + dp[4] + dp[5] + dp[6]) / 6
= 1 + 6 = 7Input: N = 10
Output: 7.36111
Approach: An approach based on dynamic programming has already been discussed in an earlier post. In this article, a more optimized method to solve this problem will be discussed. The idea is using a technique called Matrix-Exponentiation.
Let’s define An as the expected number of moves to reach the end of a board of length N + 1.
The recurrence relation will be:
An = 1 + (An-1 + An-2 + An-3 + An-4 + An-5 + An-6) / 6
Now, the recurrence relation needs to be converted in a suitable format.
An = 1 + (An-1 + An-2 + An-3 + An-4 + An-5 + An-6) / 6 (equation 1)
An-1 = 1 + (An-2 + An-3 + An-4 + An-5 + An-6 + An-7) / 6 (equation 2)
Subtracting 1 with 2, we get An = 7 * (An-1) / 6 – (An-7) / 6
Matrix exponentiation technique can be applied here on the above recurrence relation.
Base will be {6, 6, 6, 6, 6, 6, 0} corresponding to {A6, A5, A4…, A0}
Multiplier will be
{
{7/6, 1, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 1},
{-1/6, 0, 0, 0, 0, 0, 0}
}
To find the value:
- Find mul(N – 7)
- Find base * mul(N – 7).
- The first value of the 1 * 7 matrix will be the required answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define maxSize 50using namespace std;// Function to multiply two 7 * 7 matrixvector<vector<double> > matrix_product( vector<vector<double> > a, vector<vector<double> > b){ vector<vector<double> > c(7); for (int i = 0; i < 7; i++) c[i].resize(7, 0); for (int i = 0; i < 7; i++) for (int j = 0; j < 7; j++) for (int k = 0; k < 7; k++) c[i][j] += a[i][k] * b[k][j]; return c;}// Function to perform matrix exponentiationvector<vector<double> > mul_expo(vector<vector<double> > mul, int p){ // 7 * 7 identity matrix vector<vector<double> > s = { { 1, 0, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0, 0 }, { 0, 0, 1, 0, 0, 0, 0 }, { 0, 0, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0 }, { 0, 0, 0, 0, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 1 } }; // Loop to find the power while (p != 1) { if (p % 2 == 1) s = matrix_product(s, mul); mul = matrix_product(mul, mul); p /= 2; } return matrix_product(mul, s);}// Function to return the required countdouble expectedSteps(int x){ // Base cases if (x == 0) return 0; if (x <= 6) return 6; // Multiplier matrix vector<vector<double> > mul = { { (double)7 / 6, 1, 0, 0, 0, 0, 0 }, { 0, 0, 1, 0, 0, 0, 0 }, { 0, 0, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0 }, { 0, 0, 0, 0, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 1 }, { (double)-1 / 6, 0, 0, 0, 0, 0, 0 } }; // Finding the required multiplier // i.e mul^(X-6) mul = mul_expo(mul, x - 6); // Final answer return (mul[0][0] + mul[1][0] + mul[2][0] + mul[3][0] + mul[4][0] + mul[5][0]) * 6;}// Driver codeint main(){ int n = 10; cout << expectedSteps(n - 1); return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG{static final int maxSize = 50;// Function to multiply two 7 * 7 matrixstatic double [][] matrix_product(double [][] a, double [][] b){ double [][] c = new double[7][7]; for (int i = 0; i < 7; i++) for (int j = 0; j < 7; j++) for (int k = 0; k < 7; k++) c[i][j] += a[i][k] * b[k][j]; return c;}// Function to perform matrix exponentiationstatic double [][] mul_expo(double [][] mul, int p){ // 7 * 7 identity matrix double [][] s = {{ 1, 0, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0, 0 }, { 0, 0, 1, 0, 0, 0, 0 }, { 0, 0, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0 }, { 0, 0, 0, 0, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 1 }}; // Loop to find the power while (p != 1) { if (p % 2 == 1) s = matrix_product(s, mul); mul = matrix_product(mul, mul); p /= 2; } return matrix_product(mul, s);}// Function to return the required countstatic double expectedSteps(int x){ // Base cases if (x == 0) return 0; if (x <= 6) return 6; // Multiplier matrix double [][]mul = { { (double)7 / 6, 1, 0, 0, 0, 0, 0 }, { 0, 0, 1, 0, 0, 0, 0 }, { 0, 0, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0 }, { 0, 0, 0, 0, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 1 }, {(double) - 1 / 6, 0, 0, 0, 0, 0, 0 }}; // Finding the required multiplier // i.e mul^(X-6) mul = mul_expo(mul, x - 6); // Final answer return (mul[0][0] + mul[1][0] + mul[2][0] + mul[3][0] + mul[4][0] + mul[5][0]) * 6;}// Driver codepublic static void main(String[] args){ int n = 10; System.out.printf("%.5f",expectedSteps(n - 1));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach import numpy as npmaxSize = 50# Function to multiply two 7 * 7 matrix def matrix_product(a, b) : c = np.zeros((7, 7)); for i in range(7) : for j in range(7) : for k in range(7) : c[i][j] += a[i][k] * b[k][j]; return c# Function to perform matrix exponentiation def mul_expo(mul, p) : # 7 * 7 identity matrix s = [ [ 1, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 1 ] ]; # Loop to find the power while (p != 1) : if (p % 2 == 1) : s = matrix_product(s, mul); mul = matrix_product(mul, mul); p //= 2; return matrix_product(mul, s); # Function to return the required count def expectedSteps(x) : # Base cases if (x == 0) : return 0; if (x <= 6) : return 6; # Multiplier matrix mul = [ [ 7 / 6, 1, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 1 ], [ -1 / 6, 0, 0, 0, 0, 0, 0 ] ]; # Finding the required multiplier # i.e mul^(X-6) mul = mul_expo(mul, x - 6); # Final answer return (mul[0][0] + mul[1][0] + mul[2][0] + mul[3][0] + mul[4][0] + mul[5][0]) * 6; # Driver code if __name__ == "__main__" : n = 10; print(expectedSteps(n - 1)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG{static readonly int maxSize = 50;// Function to multiply two 7 * 7 matrixstatic double [,] matrix_product(double [,] a, double [,] b){ double [,] c = new double[7, 7]; for (int i = 0; i < 7; i++) for (int j = 0; j < 7; j++) for (int k = 0; k < 7; k++) c[i, j] += a[i, k] * b[k, j]; return c;}// Function to perform matrix exponentiationstatic double [,] mul_expo(double [,] mul, int p){ // 7 * 7 identity matrix double [,] s = {{ 1, 0, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0, 0 }, { 0, 0, 1, 0, 0, 0, 0 }, { 0, 0, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0 }, { 0, 0, 0, 0, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 1 }}; // Loop to find the power while (p != 1) { if (p % 2 == 1) s = matrix_product(s, mul); mul = matrix_product(mul, mul); p /= 2; } return matrix_product(mul, s);}// Function to return the required countstatic double expectedSteps(int x){ // Base cases if (x == 0) return 0; if (x <= 6) return 6; // Multiplier matrix double [,]mul = {{(double)7 / 6, 1, 0, 0, 0, 0, 0 }, { 0, 0, 1, 0, 0, 0, 0 }, { 0, 0, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0 }, { 0, 0, 0, 0, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 1 }, {(double) - 1 / 6, 0, 0, 0, 0, 0, 0 }}; // Finding the required multiplier // i.e mul^(X-6) mul = mul_expo(mul, x - 6); // Final answer return (mul[0, 0] + mul[1, 0] + mul[2, 0] + mul[3, 0] + mul[4, 0] + mul[5, 0]) * 6;}// Driver codepublic static void Main(String[] args){ int n = 10; Console.Write("{0:f5}", expectedSteps(n - 1));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approachvar maxSize = 50;// Function to multiply two 7 * 7 matrixfunction matrix_product(a, b){ var c = Array.from(Array(7), () => Array(7).fill(0)); for(var i = 0; i < 7; i++) for(var j = 0; j < 7; j++) for(var k = 0; k < 7; k++) c[i][j] += a[i][k] * b[k][j]; return c;}// Function to perform matrix exponentiationfunction mul_expo( mul, p){ // 7 * 7 identity matrix var s = [ [ 1, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 1 ] ]; // Loop to find the power while (p != 1) { if (p % 2 == 1) s = matrix_product(s, mul); mul = matrix_product(mul, mul); p = parseInt(p / 2); } return matrix_product(mul, s);}// Function to return the required countfunction expectedSteps(x){ // Base cases if (x == 0) return 0; if (x <= 6) return 6; // Multiplier matrix var mul = [ [ 7 / 6, 1, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 1 ], [ -1 / 6, 0, 0, 0, 0, 0, 0 ] ]; // Finding the required multiplier // i.e mul^(X-6) mul = mul_expo(mul, x - 6); // Final answer return (mul[0][0] + mul[1][0] + mul[2][0] + mul[3][0] + mul[4][0] + mul[5][0]) * 6;}// Driver codevar n = 10;document.write(expectedSteps(n - 1));// This code is contributed by rrrtnx</script> |
7.36111
Time Complexity of the above approach will be O(343 * log(N)) or simply O(log(N)).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
