Number of Ways to Paint N × 3 Grid
Real-world version: Colouring a Three-Wide PanelThe statement here is our own: the same inputs, outputs and technique.
A panel is n rows tall and three cells wide. Each cell is to be painted red, yellow or green so that no two cells sharing an edge carry the same colour.
Return how many paintings there are, given as the remainder after dividing by 1000000007.
Examples
Example 1
- Input
- n = 2
- Output
- 54
Twelve rows are legal on their own. Each of the six whose ends match allows five rows below it and each of the six with three different colours allows four, which comes to fifty-four two-row panels.
Example 2
- Input
- n = 6
- Output
- 23346
Six rows deep, the two running tallies have been stepped down five times and add to twenty-three thousand three hundred and forty-six.
Example 3
- Input
- n = 3
- Output
- 246
Three rows deep the count is two hundred and forty-six, small enough that the remainder never bites.
Constraints
- 1 <= n <= 5000
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def num_of_ways(n: int) -> int:public int numOfWays(int n)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's