Painting Fences

Posted: 6 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given ‘N’ fences. Your task is to find the total number of ways to paint fences using 2 colors only such that at most 2 adjacent fences are painted with the same color.

As the answer can be too large, return the answer modulo 10^9 + 7.

For Example:
Consider If N = 2, then there can be 4 different ways to color fences such that at most 2 adjacent fences have the same color-:
[ [0, 1],
  [1, 0],
  [1, 1],
  [0, 0] ]
Hence, the answer is 4.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’, representing the number of fences.
Output Format:
For each test case, print a single integer denoting the number of ways to paint the fences modulo 10^9 + 7.

Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^6

Time Limit: 1 sec
Approach 1

The idea is to use a recursive approach to find the total number of ways to paint the fences. Let us consider the two colors are black and white.

We have to think about two possibilities:

  1. If the last color was black, then:
    • If the second last color was black too, then we can only use white this time. Otherwise, we can use any color this time.
  2. Otherwise, if the last color was white, then:
    • If the last second color was black, then we can use any color this time. Otherwise, we can only use black.

In this approach, we are going to make a recursive function countWays(N). This function will return the total number of ways to paint N fences.

 

Algorithm:

  • Set mod as 1000000007.
  • Make a recursive function countWays(N) where the N is the number of fences. This function returns the number of ways to paint the N fences.
    • The base condition of this function is if N is less than or equal to 1, then return 2.
    • Set result1 as the value returned from countWays(N-1).
    • Set result2 as the value returned from countWays(N-2).
    • Return the sum of result1 and result2. We will take modulo of this sum with mod as it can overflow.
Try Problem