Painting Fence Algorithm

Problem Statement

The “Painting Fence Algorithm” states that you are given a fence having some posts (some wooden pieces or some other pieces) and some colors. Find out the number of ways to paint the fence such that at most only 2 adjacent fences have the same color. Since this number can be large, return the answer modulo 1000000007.

Example

Number of posts/wooden sticks = 2
Number of colors = 2

4

Explanation
You can paint both posts with different colors in 2 ways. And you have 2 ways to paint the posts with the same color. So total you have 4 ways.

Approach for Painting Fence Algorithm

Let’s start with a naive approach. We are given that we have n posts and k colors. Now we need to find the number of ways of coloring the posts such that there are at most only 2 adjacent posts with the same color. One naive approach could be if we generate all the sequences denoting the color obtained by each post. But this approach is highly inefficient and will surely result in exceeding the time limit.

So, what can be a better approach? One approach could be if we break the problem into smaller problems. Consider we know the answer for the number of posts = n-2 and n-1. Let us denote these values using F(n-2) and F(n-1) respectively. So we know that F(n-1) represents the number of ways in which at most only 2 adjacent posts can have the same color and the same is true for F(n-2). Now we consider that if we color posts at (n-1)th and nth position with the same color, we require that (n-1)th post should not have the same color as that of (n-2)nd post. This value is denoted using F(n-2). So we have considered a case where our nth post has the same color as that of the last post. We should also consider the ways where the current post and last post should not have the same color. This value is denoted using F(n-1). Now we have (k-1) ways to color nth post. Thus the total number of ways is equal to (F(n-1)+F(n-2))*(k-1).

Code

C++ code for Painting Fence Algorithm

#include <bits/stdc++.h>
using namespace std;

int main(){
  // number of posts
  int n;cin>>n;
  // number of available colors
  int k;cin>>k;
  int mod = 1000000007;
  int ways = 0;
  if(n == 1)cout<<k;
  else if(n == 2)cout<<k*k;
  else {
    int last = k*k; int lastTolast = k;
    for(int i=3;i<=n;i++){
      ways = ((last + lastTolast)*(k-1))%mod;
      lastTolast = last;
      last = ways;
    }
    cout<<ways;
  }
}

4 2

10

Java code for Painting Fence Algorithm

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	// number of posts
    int n = sc.nextInt();
    // number of available colors
    int k = sc.nextInt();
    int mod = 1000000007;
    int ways = 0;
    if(n == 1)System.out.print(k);
    else if(n == 2)System.out.print(k*k);
    else {
      int last = k*k; int lastTolast = k;
      for(int i=3;i<=n;i++){
        ways = ((last + lastTolast)*(k-1))%mod;
        lastTolast = last;
        last = ways;
      }
      System.out.print(ways);
    }
    }
}

4 2

10

Complexity Analysis

Time complexity

O(N), as we can see from the algorithm. We have used a single loop which runs until i is equal to n. Thus making n iterations, which means we have linear time complexity.

Space complexity

O(1),  as we have used a constant number of variables instead of making a DP array. This approach is more viable cause the solution for the problem is only dependent on the last two smaller problems.