Coding

Paint Fence

Asked at

Amazon

Walmart

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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 here

javascript

/**
 * @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;
    }
}

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

Let same be the number of ways to paint through the current post where the last two colors are equal, and diff the number where they differ. For the next post, newSame = diff, because three equal adjacent posts are forbidden and the new color can match only a previously different last color. newDiff = (same + diff) * (k - 1), because choose any color different from the previous one. Initialize one post as same = 0, diff = k, then iterate through n. The answer is same + diff; define the n=0 behavior explicitly if the API permits it. This recurrence runs in O(N) time and O(1) space and is clearer than enumerating k-color strings. Use modulo arithmetic if the specification requests it.

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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question