Count how many valid ways there are to paint an grid using three colors so that no two adjacent cells share a color.
Number of Ways to Paint N x 3 Grid
gfgProblem
You are given an integer n. Consider an n x 3 grid of cells. Each cell must be painted using one of three colors.
A painting is valid if no two cells that share an edge have the same color. This means adjacent cells horizontally or vertically must always have different colors.
Return the number of valid paintings of the grid.
Because the answer can be very large, return it modulo .
Notes
- Cells are considered adjacent if they share a side.
- The three colors are interchangeable; only the coloring pattern matters.
- Efficient counting is required for large
n.
Input Format
- A single integer
nrepresenting the number of rows in the grid.
Output Format
- Return one integer: the number of valid colorings of an
n x 3grid modulo .
Constraints
- The answer should be computed modulo .
- The intended solution should be efficient for large
n, so brute force enumeration is not feasible.
Example 1
Input
n = 1
Output
12
Explanation
For a single row of 3 cells, the first cell has 3 choices, the second has 2 choices, and the third has 2 choices, giving 3 × 2 × 2 = 12 valid colorings.
Example 2
Input
n = 2
Output
54
Explanation
There are 12 valid ways to paint the first row. For each row pattern, count how many valid second-row patterns can follow it. Summing all valid transitions gives 54.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.