Problem · Dynamic Programming
Coloring Houses
Learn this problem● Medium
SnowflakeINTERNOA
See Snowflake hiring insightsSnowflakeINTERNOAProblem statement
The city of Hackerland can be represented with an even number n houses arranged in a row. A painter must paint the houses using at most three colors. The following conditions must hold true:
n=6 then houses will be [1,2,3,4,5,6], so the houses at the same distance from both the ends will be [1,6], [2,5], [3,4].
The task is to find the number of ways to paint the houses using at most three colors such that both the above conditions hold true. Since the answer can be large, report it modulo 10^9 + 7. Two ways are considered different if at least one house is colored differently.
Function
countWaysToColorHouses(n: int) → int
Complete the countWaysToColorHouses function in the editor.
countWaysToColorHouses takes in a single parameter:
int n, the number of houses
Examples
Example 1
n = 4return = 18For (color1, color2, color3, color2)
(color1, color3, color1, color3)
The number of ways to paint 4 houses using three colors is 18. Return 18 modulo
n = 4, some of the possible valid arrangements are:
(10^9 + 7) which is 18.Example 2
n = 2return = 6The valid arrangements for 2 houses are:
(color1, color2)
(color1, color3)
(color2, color1)
(color3, color1)
(color2, color3)
(color3, color2)
Example 3
n = 4return = 18Total valid arrangements for 4 hourses are 18.
Some of the valid arrangements are:
{color1, color2, color1, color2}
{color1, color3, color1, color3}
{color2, color1, color2, color1}
{color3, color1, color3, color1}
{color2, color3, color2, color3}
{color3, color2, color3, color2}