Matrix Exponentiation

Hard
0/120
Average time to solve is 40m
profile
Contributed by
1 upvote
Asked in companies
DirectiCodenation

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
2
8
Sample Output 1:
1
1
Explanation of Sample Input 1:
Test case 1:

Here the answer is equal to the expected number of dice rolls to get the first 1 as an outcome because we cannot go outside the array. And the expected number of dice rolls to get the first '1' is 6. i.e. On average, we need to roll a dice 6 times to get at position 2.

Test case 2.
If we are 7 steps away, then we can get from 1 by getting '6' with probability (1 / 6) and expected dice roll equal to 6, similarly, from 2 we can get 5, from 3 by 4, and so on. with all same probability i.e. 1 / 6 and expected no. of dice roll 6. Now the average value will be 1 + ( (6 * 6) / 6 = 7.
Hence, for 7 steps away, our answer is 7.
Sample Input 2:
1
3
Sample Output 2:
1
Explanation of Sample Input 2:
Test case 1:
As the Input is less than 7, the expected number of operations will be 6.
Hint

Use Matrix Exponentiaiton.

Approaches (1)
Matrix Exponentiation Approach

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
  • 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.
Time Complexity

O( log(N)) where N is the given input.


For matrix multiplication, we need 7 ^ 3 iterations i.e. 343 iterations. For matrix exponentiation, we need (log N) interactions. Hence overall time complexity is O(343 * log(N)) which can be generalized down to O(logN).

Space Complexity

O(1).

 

Here, we use constant space variables. So, our space complexity is O(1).

Code Solution
(100% EXP penalty)
Matrix Exponentiation
Full screen
Console