Paint Fence
Amazon
WalmartThe problem
You are painting a fence of n posts with k different colors. You must paint the posts following these rules:
- Every post must be painted exactly one color.
- There cannot be three or more consecutive posts with the same color. Given the two integers n and k, return the number of ways you can paint the fence.
Input: n = 3, k = 2 Output: 6 Explanation: All the possibilities are shown. Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.
Input: n = 1, k = 1 Output: 1 Explanation: There is only one possibility.
Input: n = 7, k = 2
1 <= n <= 50 1 <= k <= 105 The testcases are generated such that the answer is in the range [0, 231 - 1] for the given n and k.
cpp
class Solution {
public:
int numWays(int n, int k) {
// Your code goes here
}
};java
class Solution {
public int numWays(int n, int k) {
// Your code goes here
}
}python
class Solution(object):
def numWays(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
# Your code goes herejavascript
/**
* @param {number} n
* @param {number} k
* @return {number}
*/
var numWays = function(n, k) {
// Your code goes here
};csharp
public class Solution {
public int numWays(int n, int k) {
if (k == 0 || n == 0)
{
return 0;
}
long prev_same = 0;
long prev_diff = k;
for (int i = 2; i <= n; i++)
{
long current_same = prev_diff;
long current_diff = (prev_same + prev_diff) * (k - 1);
prev_same = current_same;
prev_diff = current_diff;
}
long total_ways = prev_same + prev_diff;
return (int)total_ways;
}
}go
func numWays(n int, k int) int {
// Your code goes here
}Stuck? Show a way to structure it+
- 01Handle zero and one post base cases.
- 02Track ways ending with same and different colors.
- 03Transition same from prior different only.
- 04Transition different from all prior ways times k minus one.
- 05Return their sum.
Reference answer
Then expect these follow-ups
What if no adjacent colors may match?
Tests: recurrence change
How do you support arbitrary run limit r?
Tests: state expansion
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question