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.
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.
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.
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.
You do not need to print anything. It has already been taken care of. Just implement the given function.
1 <= T <= 10 1 <= N <= 10^6 Time Limit: 1 sec
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.
- 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.