Problem Link - Easy Tiling
Problem Statement
We wish to tile a grid of size N * 2 using 2*1 dominoes (either vertically or horizontally). The task is to find the number of distinct ways to tile the grid, and output the result mod 10^9 + 7.
Approach
The problem is equivalent to finding the (N+1) th Fibonacci number. The reasoning is:
- For an N*2 grid, you can either place a vertical domino (leaving an (N-1)*2 grid) or two horizontal dominoes (leaving an (N-2)*2 grid).
To solve efficiently, we use matrix exponentiation to compute Fibonacci numbers. The transformation matrix:
is raised to the power of N-1 using binary exponentiation, making it more efficient with O(log N) time.
Time Complexity
The time complexity is O(log N) due to matrix exponentiation.
Space Complexity
The space complexity is O(1) apart from input/output storage.