Last Updated: 6 Dec, 2020
Painting Fences
Moderate
Asked in companies
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
Approaches
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:
- 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.
- 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.
As discussed in the previous approach, we are using a recursive approach to find the total number of ways to paint the fences. In this approach, we will use memoization to reduce our time complexity by storing the solutions in the dynamic array. We have to maintain an array dpArray of size N+1. If we had already calculated the ways for a particular value of N then we can return dpArray[N] in that case instead of calculating the total number of ways again.
Algorithm:
- Set mod as 1000000007.
- Make a recursive function findWays(N,dpArray) where the N is the number of fences, and dpArray is the memoization array. 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
- We will return 2.
- Check If dpArray[N] is not equal to -1.
- We will return dpArray[N].
- Set result1 as the value returned from findWays(N-1, dpArray).
- Set result2 as the value returned from findWays(N-2, dpArray).
- Set dpArray[N] as the sum of result1 and result2. We will take modulo of this sum with mod as it can overflow.
- Return dpArray[N].
- The base condition of this function is if N is less than or equal to 1
- Make a function countWays(N) where the N is the number of fences. This function returns the number of ways to paint the N fences.
- Make a dpArray of size N+1 and initialize all its elements with -1.
- Return the value returned by function findWays(N, dpArray).
We will maintain two variables prev and curr, to find the total number of ways to paint the fences. We will initialize prev and curr as 2. We will traverse ind from 2 to N.
- We will find the number of ways to paint ind fences, which is equal to the sum of curr and prev. We will set temp as the sum of curr and prev.
- We will update the variable prev as curr and curr as temp.
In the end, the variable curr stores the number of ways to paint N fences. We will return the variable curr.
Algorithm:
- Set mod as 1000000007.
- Make a function countWays(N) where the N is the number of fences to paint. This function returns the number of ways to paint N fences.
- Set curr as 2.
- Set prev as 2.
- Iterate ind from 2 to N.
- Set temp as the sum of curr and prev. We will take modulo of this sum with mod as the sum can overflow.
- Set prev as curr.
- Set curr as temp.
- Return curr, which is our required number of ways to paint N fences.
Similar problems