Painting Fences
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

Question

Painting Fences

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

Accepted Answer

Dynamic Programming

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.

Space Complexity: O(1)Explanation:

O(1).

Constant space is being used. Hence, the overall space complexity is O(1).

Time Complexity: O(n)Explanation:

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

We are traversing from 2 to N to find the total number of ways to paint fences, which takes O(N) time. Hence, the overall time complexity is O(N).

C++ (g++ 5.4)

/*

Time Complexity: O(N) 

Space Complexity: O(1)



where N is the number of fences.

*/



int mod = 1000000007;



int countWays(int n)

{

    // Set the variables curr and prev as 2

    int curr = 2;

    int prev = 2;

    

    // Traverse ind from 2 to n

    for(int ind = 2; ind < n + 1; ind++)

    {   

        int temp = (curr + prev) % mod;

        prev = curr;

        curr = temp;

    }

        

    // Return the number of ways to paint n fences

    return curr;

}

Python (3.5)

"""

Time Complexity: O(N) 

Space Complexity: O(1)



where N is the number of fences.

"""



mod = 1000000007



def countWays(n):



    # Set the variables curr and prev as 2

    curr = 2

    prev = 2

    

    # Traverse ind from 2 to n

    for ind in range(2, n + 1):

        

        temp = (curr + prev) % mod

        prev = curr 

        curr = temp

        

    # Return the number of ways to paint n fences

    return curr

Java (SE 1.8)


/*
	Time Complexity: O(N) 
	Space Complexity: O(1)
	
	where N is the number of fences.
*/

public class Solution {

	static int mod = 1000000007;

	public static int countWays(int n) {

		// Set the variables curr and prev as 2
		int curr = 2;
		int prev = 2;

		// Traverse ind from 2 to n
		for (int ind = 2; ind < n + 1; ind++) {
			int temp = (curr + prev) % mod;
			prev = curr;
			curr = temp;
		}

		// Return the number of ways to paint n fences
		return curr;
	}

}

Accepted Answer

First I had couple of greedy solutions in mind, later on analysis I tried applying dynamic programming approach.
It was working.

Accepted Answer

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:

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.

Space Complexity: OtherExplanation:

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).

Time Complexity: OtherExplanation:

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).

Accepted Answer

Memoization

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].
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).

Space Complexity: O(n)Explanation:

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

The space complexity O(N) is needed for the memoization array and the recursion stack. Hence, the overall space complexity is O(N).

Time Complexity: O(n)Explanation:

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

The time complexity O(N) is used to find the total number of ways to paint the fences in this approach. Hence, the overall time complexity is O(N).

C++ (g++ 5.4)

/*

Time Complexity: O(N) 

Space Complexity: O(N)



where N is the number of fences.

*/



int mod = 1000000007;



int findWays(int n, vector &dpArray)

{

    // Base condition

    if(n <= 1)

    {

        return 2;

    }



    if(dpArray[n] != -1)

    {

        return dpArray[n];

    }



    // Recursive calls for values n-1 and n-2

    int result1 = findWays(n - 1, dpArray);

    int result2 = findWays(n - 2, dpArray);



    dpArray[n] = (result1 + result2) % mod;



    // Return the number of ways to paint n fences

    return dpArray[n];

}



int countWays(int n)

{

    // Make a dynanmic array

    vector dpArray(n + 1, -1);



    // Return total number of ways to paint n fences

    return findWays(n, dpArray);

}

Java (SE 1.8)


/*
	Time Complexity: O(N) 
	Space Complexity: O(N)
	
	where N is the number of fences.
*/

import java.util.Arrays;

public class Solution {

	static int mod = 1000000007;

	public static int findWays(int n, int[] dpArray) {
		// Base condition
		if (n <= 1) {
			return 2;
		}

		if (dpArray[n] != -1) {
			return dpArray[n];
		}

		// Recursive calls for values n-1 and n-2
		int result1 = findWays(n - 1, dpArray);
		int result2 = findWays(n - 2, dpArray);

		dpArray[n] = (result1 + result2) % mod;

		// Return the number of ways to paint n fences
		return dpArray[n];
	}

	public static int countWays(int n) {

		// Make a dynamic array
		int[] dpArray = new int[n + 1];
		Arrays.fill(dpArray, -1);

		// Return total number of ways to paint n fences
		return findWays(n, dpArray);
	}

}

Python (3.5)

"""

Time Complexity: O(N) 

Space Complexity: O(N)



where N is the number of fences.

"""



mod = 1000000007



def findWays(n, dpArray):



    # Base condition

    if(n <= 1):

        return 2



    if(dpArray[n] != -1):

        return dpArray[n]



    # Recursive calls for values n-1 and n-2

    result1 = findWays(n - 1, dpArray)

    result2 = findWays(n - 2, dpArray)



    dpArray[n] = (result1 + result2) % mod



    # Return the number of ways to paint n fences

    return dpArray[n]



def countWays(n):



    # Make a dynanmic array

    dpArray = [-1 for i in range(n + 1)]



    # Return total number of ways to paint n fences

    return findWays(n, dpArray)

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:

Input Format:

Output Format:

Note:

Constraints:

Top PayPal Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in PayPal Software Engineer