Tiling Problem Statement

Given a board with 2 rows and N columns, and an infinite supply of 2x1 tiles, determine the number of distinct ways to completely cover the board using these tiles.

You can place each tile:
1. Horizontally as a 1x2 tile
2. Vertically as a 2x1 tile

Input:

N

Output:

The number of ways to tile the board modulo 10^9 + 7

Example:

Input:

N = 4

Output:

5

Explanation:

The image shows an example of possible tile arrangements for a board size of N = 4. The board is completely covered using the available tiles in multiple distinct configurations.

Constraints:

1

Question

Tiling Problem Statement

Given a board with 2 rows and N columns, and an infinite supply of 2x1 tiles, determine the number of distinct ways to completely cover the board using these tiles.

You can place each tile:
1. Horizontally as a 1x2 tile
2. Vertically as a 2x1 tile

Input:

Output:

The number of ways to tile the board modulo 10^9 + 7

Example:

Input:

N = 4

Output:

Explanation:

The image shows an example of possible tile arrangements for a board size of N = 4. The board is completely covered using the available tiles in multiple distinct configurations.

Constraints:

1 <= N <= 10¹⁸
Time limit: 1 sec

Note:

You are not required to print the output explicitly, just implement the function as the printing is handled by the system.

Accepted Answer

The problem involves finding the number of ways to tile a 2xN board using 2x1 tiles.

Use dynamic programming to solve this problem efficiently.
Define a recursive function to calculate the number of ways to tile the board.
Consider both horizontal and vertical placements of tiles.
Implement the function to handle large values of N using modulo arithmetic.
Example: For N = 4, the number of ways to tile the board is 5.

Accepted Answer

class solution {

static int getNoOfWays(int n)

{

// Base case

if (n <= 2) {

return n;

}

return getNoOfWays(n - 1) + getNoOfWays(n - 2);

}

// Driver Function

public static void main(String[] args)

{

System.out.println(getNoOfWays(4));

System.out.println(getNoOfWays(3));

}