Given a n x 4 matrix where n is a positive number, find number of ways to fill the matrix with 1 x 4 tiles.

For example, there are 3 ways to place `1 x 4`

tiles in a `5 x 4`

matrix –

- Place all 5 tiles horizontally.

- Place 4 tiles vertically in the first four rows and 1 tile horizontally in the last row.

- Place 1 tile horizontally in the first row and adjust 4 tiles vertically in the remaining rows.

Similarly, there are 4 ways to place `1 x 4`

tiles in a `6 x 4`

matrix –

- Place all 6 tiles horizontally.

- Place 4 tiles vertically in the first four rows and remaining 2 tiles horizontally in the last two rows.

- Place 2 tiles horizontally in the first two rows and adjust the remaining 4 tiles vertically in the remaining rows.

- Place 2 tiles horizontally in the first & the last row and adjust the remaining 4 tiles vertically in the middle rows.

From the above examples, it is evident that a single tile can be placed horizontally or 4 tiles can be placed together vertically (since the matrix has dimensions `n x 4`

). So the problem of computing the number of ways `T(n)`

for a `n x 4`

matrix can be broken down into the subproblems of computing `T(n-1)`

and `T(n-4)`

, and then adding the two. Considering this, the recurrence relation `T(n)`

can be written as:

`T(n) = T(n-1) + T(n-4) where n > 4 and`

`T(1) = T(2) = T(3) = 1 // all tiles can be placed only horizontally for n <= 3`

`T(4) = 2 // all tiles can be placed either horizontally or vertically.`

Here's a C program that implements the above recurrence:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <stdio.h> // Recursive function to find number of ways to fill a n x 4 matrix // with 1 x 4 tiles int totalWays(int n) { // base cases if (n < 1) return 0; if (n < 4) return 1; if (n == 4) return 2; // combine results of placing a tile horizontally and // placing 4 tiles vertically return totalWays(n - 1) + totalWays(n - 4); } // main function int main(void) { int n = 5; printf("Total number of ways are %d", totalWays(n)); return 0; } |

`Output:`

Total number of ways are 3

The time complexity of above solution is exponential since it computes solutions to the same sub-problems again and again i.e. the problem exhibits overlapping subproblems.

We can easily solve this problem using Dynamic Programming. The idea is to construct a temporary array which stores the results of each sub-problem using already computed results of the smaller sub-problems. The algorithm can be implemented as follows in C:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <stdio.h> // Function to find number of ways to fill a n x 4 matrix with 1 x 4 tiles int totalWays(int n) { // base case if (n < 1) return 0; if (n < 4) return 1; // construct a temporary array T[] such that T[i] stores the // number of ways to fill an (i x 4) grid int T[n + 1]; // handle separately for n <= 4 T[1] = T[2] = T[3] = 1; T[4] = 2; // fill the array in bottom-up fashion for (int i = 5; i <= n; i++) { // place a single tile horizontally or 4 tiles vertically together T[i] = T[i - 1] + T[i - 4]; } return T[n]; } // main function int main(void) { int n = 5; printf("Total number of ways are %d", totalWays(n)); return 0; } |

`Output:`

Total number of ways are 3

The time complexity of above solution is `O(n)`

and auxiliary space used by it `O(n)`

. The program can be made to run in constant space by storing solutions to only last four sub-problems at any point and discarding the rest. The space efficient implementation is left as an exercise to the readers.

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply