Dominos Arrangement

Hard
0/120
2 upvotes

Problem statement

Ninja is playing with dominos. The size of each domino is 2*1. He has a rectangular box of size 3*’N’.Ninja wants to know how many ways Ninja can tile dominos into the box such that the box is completely filled. Can you help Ninja to find a number of ways?The answer can be very large, so return answer % (10^9 +7).

For Example 
If the ‘N’ is 3. The number of ways will be 2 shown below:

altImage

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer, ‘N’, denoting the length of the box.
Output Format: 
For each test case, print the number of ways.

Print the output of each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 100000. 

Time limit: 1 sec
Sample Input 1:
2 
2
3
Sample Output 1:
3
0
Explanation of sample input 1:
For the first test case,

The number of ways to fill 2*1 dominos into a 3*2 is 3.Hence, the answer is 3.
The different ways are shown below:

altImage

For the second test case:

There are no possible ways to fill the box having size 3*3. Hence, the answer is 0.
Sample Input 2:
2
4
8
Sample Output 2:
11
153
Hint

Think of a pattern and break the problem into smaller subproblems.

Approaches (3)
Recursion

Intution: Lets denote U[n] is the number of ways to fill the box of size 3*N using the dominos.

and V[n] is defined as the number ways to fill the 3*n rectangle box without a lower left corner.


 

             


 

U[n] can be break into smaller subproblems as  U[n-2] + V[n-1] + V[n-1] shown in the figure below.

 


 

V[n] can be similarly break into smaller subproblems as V[n-2] +U[n-1] shown in the figure below.

 


 

So, using these all relations ,the final recursive realtion is U[n] = U[n-2] + 2*V[n-1] and V[n] = U[n-1] + V[n-2].


 

Base Cases will be :


 

So, using these equations we will define two functions findU(n) that will return the value of U[n] and findV(n) that will return the value of V[n] as described above.At last,we will return the value of findU(n) corresponding to the final answer.



 

Algorithm:

 

  • Define findU(n) function that will return the number of ways to fill the box of size 3*N using the dominos.
    • If N==1:
      • Return 0.
    • If N==2:
      • Return 3.
    • Return ( findU(n-2) + 2*findV(n-1))% (10^9 +7).
  • Define findV(n) function that will return the number of ways to fill the 3*n rectangle box without lower-left corners.
    • If N==1:
      • Return 1.
    • If N==2:
      • Return 0.
    • Return ( findV(n-2) + findU(n-1))% (10^9 +7).
  • Return findU(n) corresponding to the final answer.
Time Complexity

O(2^N), where ‘N’ is the length of the box.

 

In this approach, we are using recursive functions to calculate the number of ways. Each recursive functions make two more recursive calls. So, the total number of calls will be 2^N. Hence, the overall time complexity is O(2^N).

Space Complexity

O(N), where ‘N’ is the length of the box.

 

In this approach, we are using recursive functions. So a space of O(N) will be occupied by stack memory. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Dominos Arrangement
Full screen
Console