Painting Fences

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
13 upvotes
Asked in companies
AmazonPayPalCodenation

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2
3
Sample Output 1 :
4
6
Explanation:
For test case 1: 
In this case, N = 2, so the total number of ways to color fences using 2 colors is 4
[ [0, 0],
  [1, 1],
  [0, 1],
  [1, 0] ]
Hence, the answer is 4.

For test case 2: 
In this case, N = 3, so the total number of ways to color fences using 2 colors is 6.
[ [0, 1, 1],
  [1, 0, 0],
  [0, 1, 0],
  [1, 0, 1],
  [0, 0, 1],
  [1, 1, 0] ]
Hence, the answer is 6.
Sample Input 2:
2
4
5
Sample Output 2 :
10
16
Hint

Try to think of a recursive approach.

Approaches (3)
Recursion

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.
Time Complexity

O(2^N) where N is the number of fences.


Each function makes two recursive calls, and the total number of recursive calls in the worst case is 2^N. Hence, the overall time complexity is O(2^N). 

Space Complexity

O(N) where N is the number of fences.

 

The space complexity O(N) is needed for the recursion stack in the worst case. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Painting Fences
Full screen
Console