Last Updated: 27 Jun, 2021
Matrix Exponentiation
Hard
Asked in companies
Ninja is playing a game, he is standing on index 1 in a linear array of size ‘N’, then he rolls a dice and moves forward according to the number on the top of the dice. He repeats this operation until he reached index ‘N’. He asked you to find the expected number of moves required to reach position ‘N’ starting from ‘1’.
Note:
1. The expected number of moves can be fractional.
2. Ninja cannot go outside the array i.e if he is at (n - 1)-th position he can only move if he gets 1 as an outcome in dice.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains one integer, ‘N’, denoting the size of the board.
Output Format:
For each test case, return a double value. If the returned value is correct with an error margin of 0.001 to -0.001. then the output will be 1 else 0.
Note:
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 10^9
Time Limit: 1 sec.
Approaches
Here, as we know that dice can give us 6 moves, so we can reach a particular step from its previous 6 steps. The expected number of dice rolls required to get '1' as an outcome is 6. similarly for getting ‘2’, ‘3’, '4', '5', ‘6’ is also 6. We can reach at position ‘n’ from ‘n - 1’ by getting ‘1’, from ‘n - 2’ by getting 2, and so on. Thus the expected dice rolls required to get at position ‘n' is 1 more than the average dice roll required to get at the previous 6 positions.
The Recurrence relation can be described as:
A[n] = 1 + ( A[n - 1] + A[n - 2] + A[n - 3] + A[n - 4] + A[n - 5] + A[n - 6] ) / 6.
This can be observed as extended Fibonacci series, we can apply Matrix Exponential technique to the above relation to find the answer.
A[n - 1] = 1+ (A[n - 2] + A[n - 3] + A[n - 4] + A[n - 5] + A[n - 6] + A[n - 7]) / 6
Substracing A[n - 1] from A[n], we get.
A[n] = 7 * (A[n - 1]) / 6 - (A[n - 7]) / 6
The matrix multiplier is as follows:
[[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 ]]
Algorithm:
- Decrement n by 1 as we have to cover n - 1 steps to reach n from 1.
- If n is less than 7, return 6
- Declare a matrix multiplier ‘mul’ and set its value
- Call a function ‘matExpo(mul , N)’ to find (mul ^ N).
- Calculate 'ans' equal to the sum of the first six elements of the first column of the matrix and divide it by 6
- Return ‘ans’
Description of matExpo function('mul', ‘n’):
- Declare an identity matrix S
- Run a while loop which will terminate when n is not equal to 1.
- If ‘n’ is odd
- Call function 'matrixProduct' with parameters as ‘S’ and ‘mul’
- Call function ‘matrixProduct’ with parameters as ‘mul’ and ‘mul’
- Divide ‘n’ by 2
- If ‘n’ is odd
- Call function matrixProduct(mul, s) and return its value to the parent function
Discription of matrixProduct function('a', 'b'):
Returns the product of matrix ‘a’ and matrix ‘b’.
- Declare an empty matrix ‘temp’ to store the product of the two matrices passed in function parameters
- Run 3 nested loops with i, j, k as loop counters running from 0 to 7.
- Update temp[i][j] with sum of temp[i][j] + a[i][k] * b[k][j]
- Return the 'temp' matrix.
Similar problems