1. Horizontally as 1x2 tile
2. Vertically as 2x1 tile
The number of ways might be large so output your answer modulo 10^9 + 7.
The first and only line of each test case contains an Integer 'N' which denotes the size of the board, i.e. '2' rows and 'N' columns.
For each test case, print the number of ways to tile the board modulo 10^9 + 7.
You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
1 <= N <= 10^18
Where 'N' is the number of columns in the board.
Time limit: 1 sec
Try to place the tile to fill the unit column and calculate the number of ways from smaller sub-problems. Then use memoization to convert O(2^N) solution to an O(N) solution.
We can place in this way where we have ‘idx-1’ column filled.
2. Option 2 - 2 Vertical Tiles
We can place in this way where we have ‘idx-2’ column filled.
2. So, numberOfWays(n) = numberOfWays(n-1) + numberOfWays(n-2)
3. Base cases are:
Try to place the tile to fill the unit column and calculate the number of ways from smaller sub-problems. We can use bottom-up DP with keeping the previous two values.
We can place in this way where we have ‘idx-1’ column filled.
2. Option 2 - 2 Vertical Tiles
We can place in this way where we have ‘idx-2’ column filled.
2. So, numberOfWaysCur = numberOfWaysPre1 + numberOfWaysPre2
numberOfWaysPre2 = 1
When n = 2 there are two ways - Placing 2 Vertical Tile and Placing 2 Horizontal Tiles
numberOfWaysPre1 = 2
5.Now Iterate from i=3 to N and keep updating the three variables.
6.Also, take care of overflow using modulo 10^9 + 7.
We can observe that the solution of this problem for 2xN Board is (N-1)th Fibonacci Number.
We can calculate the ‘N’th Fibonacci Number using Binary Matrix Exponentiation explained below. Here, Fn represents the n'th Fibonacci number. We will raise the matrix to the power of (n - 1) so that the top-left element gives the value of F(n + 1 - 1) = F(n).
[[1 1] (pow n) [[(F(n+1) F(n)]
[1 0]] = [F(n) F(n-1)]]