Tiling Problem
You have been given a board where there are '2' rows and 'N' columns. You have an infinite supply of 2x1 tiles, and you can place a tile in the following ways:

1. Horizontally as 1x2 tile 2. Vertically as 2x1 tile

Count the number of ways to tile the given board using the available tiles.

Note :

The number of ways might be large so output your answer modulo 10^9 + 7.

Here an example of tile and board for 'N' = 4 :

Input format :

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.

Output format :

For each test case, print the number of ways to tile the board modulo 10^9 + 7.

Note:

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Constraints :

1

Question

Tiling Problem

You have been given a board where there are '2' rows and 'N' columns. You have an infinite supply of 2x1 tiles, and you can place a tile in the following ways:

1. Horizontally as 1x2 tile
2. Vertically as 2x1 tile

Count the number of ways to tile the given board using the available tiles.

Note :

The number of ways might be large so output your answer modulo 10^9 + 7.

Here an example of tile and board for 'N' = 4 :

Tiling Example

Input format :

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.

Output format :

For each test case, print the number of ways to tile the board modulo 10^9 + 7.

Note:

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Constraints :

1 <= N <= 10^18

Where 'N' is the number of columns in the board. 

Time limit: 1 sec

Accepted Answer

Recursion And Memoization (Runtime error)

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.

At any point we are at ‘idx’ column then we can place our tile in two ways to fill this column.
1. Option 1 - 1 Horizontal Tile

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:

When n = 1 there is only 1 way - Placing 1 Vertical Tile
When n = 2 there are two ways - Placing 2 Vertical Tile and Placing 2 Horizontal Tiles.
Also, take care of overflow using modulo 10^9 + 7.
Lastly, use a DP Array of size N for memoization to save time over repetitive calls.

Space Complexity: O(n)Explanation:

O(N), where N is the number of columns in the board.

We are using DP Matrix of Space Complexity O(N) to store solutions. Hence, the overall Space Complexity is O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the number of columns in the board.

As we are using the Dynamic Programming Approach and at max, we can have N different calls so, Overall Time Complexity is O(N).

Accepted Answer

Iterative DP

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.

At any point we are at ‘idx’ column then we can place our tile in two ways to fill this column.
1. Option 1 - 1 Horizontal Tile

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

Where numberOfWaysCur is the number of ways to tile till 'current' column in the board.
Where numberOfWaysPre1 is the number of ways to tile till 'current-1' column in the board.
Where numberOfWaysPre2 is the number of ways to tile till 'current-2' column in the board.
Base cases are:When n = 1 there is only one way - Placing 1 Vertical Tile

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.

Space Complexity: O(1)Explanation:

O(1).

Constant space is being used. Hence, the overall Space Complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), where N is the number of columns in the board.

As we are using the Dynamic Programming Approach and looping over N that takes O(N) time. Hence, the overall Time Complexity is O(N).

Accepted Answer

Matrix Exponentiation

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)]]

So we need to find the (N - 1)th Power of this Matrix.
We can write a function for the multiplication of two matrices.
Then we can use binary exponentiation to calculate the ‘N’ power of this Matrix in log(N).
Binary Exponentiation / Fast Exponentiation:

long long binpow(Matrix a, long long b) {

if (b == 0)

return 1;

Matrix res = binpow(a, b / 2);

if (b % 2)

return res * res * a;

else

return res * res;

}

Similarly, we can write a version for Matrix Exponentiation.
Take care of overflow using modulo by 10^9 + 7 at each operation of Matrix Multiplication.

Space Complexity: O(1)Explanation:

O(log(N)), where N is the number of columns in the board.

The Space Complexity O(log(N)) is required by the recursion stack. Hence, the overall Space Complexity is O(log(N)).

Time Complexity: O(logn)Explanation:

O(log(N)), where N is the number of columns in the board.

As we are diving N by 2 till it becomes 0, so that’s log(N) times multiplication of 2*2 Matrix. So Overall Time Complexity is O(log(N)).

You have been given a board where there are '2' rows and 'N' columns. You have an infinite supply of 2x1 tiles, and you can place a tile in the following ways:

Count the number of ways to tile the given board using the available tiles.

Note :

Here an example of tile and board for 'N' = 4 :

Input format :

Output format :

Note:

Constraints :

Top Adobe Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern