Last Updated: 6 Dec, 2021
Lego Blocks
Easy
Asked in companies
You have two kinds of Lego blocks (see image below) and an infinite supply of both. There is a platform of empty cells made up of 2 rows and ‘N’ columns. You must place the Lego blocks on the platform in such a way such that -
1. Every cell on the platform is covered
2. No two Lego blocks overlap
3. No Lego block is placed in such a way that it goes out of the boundary of the platform.
If Lego blocks are placed such that all three conditions above are satisfied, it is called a Valid placing. Your task is to count the number of Valid ways to place the Lego blocks. Since this number might be extremely large, print it modulo (10^9+7).
Note: The blocks can be rotated. Two valid placings are considered different if there’s at least one lego block whose position differs in both placings. (See samples for better understanding).
Input Format:
The first line contains 'T', denoting the number of test cases.
For each Test :
The first line contains a single integer ‘N’, denoting the number of columns on the platform.
Output Format:
For each test, print an integer, denoting the number of valid ways to place the Lego blocks modulo (10^9 + 7).
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= T <= 10
1 <= N <= 10^5
The sum of 'N' all test cases does not exceed 10^5.
Time Limit: 1 sec
Approaches
Approach: We have two kinds of blocks. At each point, we can place the blue block either horizontally or vertically and we can place the red block in four different configurations as shown in the sample test case explanation for ‘N’ = 3.
We try each of these 6 configurations until we either exceed the boundary of the platform, or get one valid placing. We can recursively count the number of such placings.
Algorithm:
- Initialize ‘ans’ with 0
- Declare a boolean array of size 2*N and fill it with 0s. This represents how much of our platform is currently covered.
- Recursively do the following from i=1 to N
- Try all 6 possible configurations based on how much current platform is covered
- If current placing exceeds platform boundary, return
- If all N columns have been perfectly filled, increment ‘ans’ by 1 and return.
- Return ‘ans’ modulo (10^9+7)
Approach: After some placing of the blocks, there can be two scenarios. Either the N columns are completely filled, or the last column is partially filled. If the last column is partially filled, it means either the upper cell or the lower cell is filled. However, we don’t need to consider these cases separately as they are horizontally symmetric.
Now, we need to compute two things for each ‘i’ :
F[i] = Number of valid placings such that ‘i’ columns are fully covered
P[i] = Number of valid placings such that ‘i’th column is partially covered
At the ‘i’th column, to make it fully filled,we can place blocks like this:
- If (i-1) columns are fully filled, one vertical blue block
- If (i-2) columns are filled, two horizontal blue blocks
- If the (i-1)th row is partially filled, one red block (Upper cell or lower cell, 2 ways)
Therefore:
F[i] = F[i-1] + F[i-2] + (2*P[i-1])
At the ‘i’th column, to make it partially filled,we can place blocks like this:
- If the (i-1)th row is partially filled, one blue block horizontally
- If (i-2) columns are filled, one red block
Therefore:
P[i] = P[i-1] + F[i-2]
Algorithm:
- Declare 2 arrays of size ‘N’, F and P
- Initialise the following for base cases
- F[1]=1, F[2]=2, P[1]=0, P[2]=1
- Iterate a loop i =3 to N
- F[i] = F[i-1] + F[i-2] + (2*P[i-1])
- P[i] = P[i-1] + F[i-2]
- Return F[N] modulo (10^9+7)