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

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

}