Problem

Submissions

Hints & solutions

Discuss

Lego Blocks

Easy

0/40

Average time to solve is 20m

Contributed by

5 upvotes

Asked in companies

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
1
3

Sample Output 1

1
5

Explanation for Sample Input 1:

For case 1:
The only valid placing for ‘N’ = 1 is just one blue Lego block placed vertically.

For Case 2:
The 5 valid placing for ‘N’ = 3 are shown below

Sample Input 2:

2
2
5

Sample Output 2:

2
2
24

Hint 1

Hint 2

Recursively try and place blocks.

Approaches (2)

Approach 1

Approach 2

Brute Force

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)

Time Complexity

O(6^N), where ‘N’ is the number of columns.

Since from each function call, we make a max of another 6 calls, it is 6^N in the worst case. Hence the overall complexity is O(2^N).

Space Complexity

O(N), where ‘N’ is the number of columns.

We declare a boolean array of size 2*N to keep track of cells covered. Hence the overall complexity is O(N).

(100% EXP penalty)

Lego Blocks

Console