You are painting a fence consisting of n posts. You have k different colors available.
Each post must be painted such that no more than two adjacent fence posts have the same color.
Given the two integers n and k, return the number of ways you can paint the fence.
Example 1:
Input: n = 3, k = 2
Output: 6
Explanation:
All possible ways are:
post1 post2 post3
---- ---- ----
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
Example 2:
Input: n = 1, k = 1
Output: 1
Example 3:
Input: n = 7, k = 2
Output: 42
Constraints:
1 <= n <= 501 <= k <= 100When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force approach to the paint fence problem is simple: we'll try every single possible way to paint the fence. This means exploring all combinations of colors for each section of the fence, ensuring we follow the rule about not having too many adjacent sections with the same color.
Here's how the algorithm would work step-by-step:
def paint_fence_brute_force(number_of_posts, number_of_colors):
if number_of_posts == 0:
return 0
valid_combinations_count = 0
def is_valid_combination(fence):
# Check for rule violations.
for i in range(len(fence) - 2):
if fence[i] == fence[i + 1] == fence[i + 2]:
return False
return True
def generate_combinations(current_fence):
nonlocal valid_combinations_count
if len(current_fence) == number_of_posts:
# Base case: fence is complete, validate it.
if is_valid_combination(current_fence):
valid_combinations_count += 1
return
# Explore all available color choices.
for color_index in range(number_of_colors):
new_fence = current_fence + [color_index]
# Recursively paint the rest of the fence.
generate_combinations(new_fence)
generate_combinations([])
return valid_combinations_countThe key to efficiently painting the fence is to realize we only need to track the last two fence post colors. Instead of exploring every painting combination, we can focus on how many ways we can paint the current post the same or a different color than the previous post and build our result based on this.
Here's how the algorithm would work step-by-step:
def paint_fence(number_of_posts, number_of_colors):
if number_of_posts == 0:
return 0
# Initialize the possibilities for first two posts.
same_color_ways = 0
different_color_ways = number_of_colors
for i in range(1, number_of_posts):
# Count ways to paint the current post same or diff.
current_same_color = different_color_ways
# If the previous two posts are different colors,
# the current post can be any color.
current_different_color = (same_color_ways + different_color_ways) * (number_of_colors - 1)
# Update for the next iteration
same_color_ways = current_same_color
different_color_ways = current_different_color
# Total ways are sum of same and diff colors.
return same_color_ways + different_color_ways| Case | How to Handle |
|---|---|
| n = 0 (No fences) | Return 0 because there are no ways to paint no fences. |
| k = 0 (No colors) | Return 0 because there are no colors to paint the fences with if n > 0 and if n = 0 it will be handled by the n=0 edge case. |
| n = 1 (One fence) | Return k because there are k possible colors for the one fence. |
| k = 1 and n > 2 (One color, more than two fences) | Return 0, as you can't have more than two fences in a row painted with the same color if k = 1 and n > 2. |
| Integer overflow when calculating the number of ways | Use long data type to handle larger results, or use modulo operation if the problem specifies a modulo. |
| Large n (number of fences) affecting memory usage and performance | The iterative dynamic programming approach efficiently uses constant space since it only needs to store the last two values. |
| k = 1 (Only one color) and n = 2 | Return 1 because the two fences must be the same color. |
| k > n (More colors than fences) | The general formula handles this correctly as the 'different' case still calculates correctly given that k > n. |