Last Updated: 29 Nov, 2021
Build Electric Poles
Moderate
Asked in company
There are ‘N’ plots on each side of a road, the plots on each side are arranged in a row. You have to find the number of ways in which you can build electric poles, there is no limit on the number of poles that you build, that is: you can even build zero poles, but you must take care that the electric poles are not built on the adjacent plots.
As the answer can be large, print its value modulo 10^9 + 7.
For Example :
If ‘N’ = 4
If “| |” represents the road, “#” represents an empty plot, and “^” represents an electric pole.
Then the following arrangements are valid:
1) # # # # | | # # # #
2) # # # ^ | | ^ # # #
3) ^ # ^ # | | # ^ # ^
4) ^ # # ^ | | ^ # # ^
In total, there are 64 valid ways to build electric poles.
Note that an arrangement like this: # # ^ ^ | | # # # # is invalid as it contains two electric poles that are adjacent to each other.
Follow Up :
Can you try to solve this problem in O(N) time and O(1) space?
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’, denoting the number of plots on each side of the road.
Output Format :
For each test case, print the number of ways in which we can build the electric poles.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 10000
Time limit: 1 sec
Approaches
Observe that building poles on one side of the road does not depend on building poles on the other side, ie: if we are able to calculate the number of ways to build the poles on one side of the road then we can simply return the square of that answer (since the result would also be the same for the other side also, and being independent we would multiply them to get the final answer). Also, notice that building poles on one side of the road are similar to building a binary string of length equal to N which doesn’t contain consecutive 1’s, where 1 corresponds to a plot with an electric pole and 0 corresponds to an empty plot.
There are 2^N binary strings possible of length equal to N, we can recursively generate all possible binary strings, we can even prune this search by using a standard backtracking technique and generate only the strings that satisfy the given condition, but in this approach, we will discuss something that is bottom-up in nature and can later be extended to memoize results and become an efficient dynamic programming solution, but for this solution, we will limit our discussion to just a simple recursion.
For each of the i’th positions, we only have two possible bits to place as this is a binary string. We are allowed to place 1 at the i’th position only when i-1’th position doesn’t contain a 1, in other words, the number of strings that will be formed by placing 1 at the i’th position is equal to the number of strings formed by placing 0 at the i-1’th position. Further, the number of strings formed by placing 0 at the i’th position is equal to the number of strings formed by placing either a 0 or a 1 at the i-1’th position. This creates a perfect recursive approach as we are recalculating things in a similar way for each of the positions in the binary string.
The steps are as follows :
- Initialize a variable ‘ans’ equal to 0, this variable stores the final answer.
- Make initial calls to the recursive function, in the first call pass the last position and 0-bit as parameters, and in the second call pass the last position and 1-bit as parameters.
- The first call returns the number of ways to build electric poles on one side of the road such that the last plot is empty.
- The second call returns the number of ways to build electric poles on one side of the road such that the last plot is non-empty (contains an electric pole).
- Modulo of the sum of these calls is the number of ways of building electric poles on one side of the road. And we will later store this value in ‘ans’.
- In the recursive function:
- Declare a base condition to end the recursion: if the current index ‘idx’ is equal to 0, then return the value equal to 1. This is because the number of binary strings of length equal to one that ends with a particular digit will be equal to 1, therefore we are returning a value 1 when ‘idx’ equals 0.
- If the current bit to be placed ‘curBit’ is equal to 0, then make recursive calls to the previous index passing ‘curBit’ equal to 0 in one call, and ‘curBit’ equal to 1 in the other call. Return the modulo of sum of these two recursive calls.
- If the current bit to be placed ‘curBit’ is equal to 1, then make a single recursive call to the previous index passing ‘curBit’ equal to 0 and return the value returned from this recursive call.
- Finally return the square of ‘ans’, to also take into account the other side of the road.
Observe that building poles on one side of the road does not depend on building poles on the other side, ie: if we are able to calculate the number of ways to build the poles on one side of the road then we can simply return the square of that answer (since the result would also be the same for the other side also, and being independent we would multiply them to get the final answer).
Another clever observation is that this question now simply becomes a standard DP question, for one side of the road, the answer equals the number of ways to build binary strings of length "N" if we can't place adjacent 1's. Finally, we will consider both sides of the road by returning the square of this answer.
To build binary strings of length ‘N’: for each of the i’th positions, we only have two possible bits to place as this is a binary string. We are allowed to place 1 at the i’th position only when i-1’th position doesn’t contain a 1, in other words, the number of strings that will be formed by placing 1 at the i’th position is equal to the number of strings formed by placing 0 at the i-1’th position. Further, the number of strings formed by placing 0 at the i’th position is equal to the sum of the number of strings formed by placing either a 0 or a 1 at the i-1’th position. This creates a perfect recursive approach as we are recalculating things in a similar way for each of the positions in the binary string.
But we can avoid the recalculations if we use a dp-table to store the number of strings of length equal to ‘X’ ending with a 0-bit or a 1-bit. This way we won’t have to recalculate things and is a standard way to memoize recursive solutions and convert them into dynamic programming.
The steps are as follows :
- Declare a 2D array ‘dp’ of size N * 2, and initialize all the values equal to -1. Here, dp[i][j] denotes the count of binary strings of length equal to ‘i’ that have the last bit equal to ‘j’. Initialize dp[0][0] and dp[0][1] equal to 1 as base conditions, this state denotes the binary string of length equal to one.
- Make initial calls to the recursive function, in the first call pass the last position and 0-bit as parameters, and in the second call pass the last position and 1-bit as parameters.
- The first call returns the number of binary strings of length equal to ‘N’ that have 0 as their last bit and don’t contain consecutive 1’s.
- The second call returns the number of binary strings of length equal to ‘N’ that have 1 as their last bit and don’t contain consecutive 1’s.
- We will later return the modulo of the sum of these calls.
- In the recursive function:
- Declare a base condition to end the recursion: if the current index ‘idx’ is equal to 0, then return the value equal to the value corresponding to the ‘dp’ matrix. This is because the number of binary strings of length equal to one that ends with a particular digit will be equal to 1, therefore we are returning a value 1 when ‘idx’ equals 0.
- If the value corresponding to the dp[idx][curBit] is not equal to -1, means we have already calculated this result and we will directly return it to avoid recalculation.
- If the current bit to be placed ‘curBit’ is equal to 0, then make recursive calls to the previous index passing ‘curBit’ equal to 0 in one call, and ‘curBit’ equal to 1 in the other call. Store the modulo of the sum of these two recursive calls in the ‘dp’ matrix.
- If the current bit to be placed ‘curBit’ is equal to 1, then make a single recursive call to the previous index passing ‘curBit’ equal to 0 and store the value returned from this recursive call in the ‘dp’ matrix.
- Finally return the value corresponding to dp[idx][curBit].
- Initialize a variable ‘ans’ equal to sum dp[N-1][0] and dp[N-1][1], this will store the final count of binary strings that don’t contain consecutive 1’s, which is also equal to the number of ways of building electric poles on one side of the road.
- Finally return the square of ‘ans’, to also take into account the other side of the road.
Observe that building poles on one side of the road does not depend on building poles on the other side, ie: if we are able to calculate the number of ways to build the poles on one side of the road then we can simply return the square of that answer (since the result would also be the same for the other side also, and being independent we would multiply them to get the final answer).
Another clever observation is that this question now simply becomes a standard DP question, for one side of the road, the answer equals the number of ways to build binary strings of length "N" if we can't place adjacent 1's. Finally, we will consider both sides of the road by returning the square of this answer.
To build binary strings of length ‘N’: for each of the i’th positions, we only have two possible bits to place as this is a binary string. We are allowed to place 1 at the i’th position only when the i-1’th position doesn’t contain a ‘1’, in other words, the number of strings that will be formed by placing 1 at the i’th position is equal to the number of strings formed by placing 0 at the i-1’th position. Further, the number of strings formed by placing 0 at the i’th position is equal to the sum of the number of strings formed by placing either a 0 or a 1 at the i-1’th position.
Let’s define our dp states now, we can define dp[i][j] equal to the count of binary strings that are of length equal to ‘i’ and contain ‘j’ as the last bit. We can define transitions as dp[i][1] = dp[i-1][0] and dp[i][1] = dp[i-1][0] + dp[i-1][1]. A clever observation here is that we need not store all the dp results for ‘i’ equal to 0 to N - 1, rather we just need to store the results of the previous index which can be done with the help of just two variables. This will save a lot of space and convert a linear space solution to a constant space solution.
The steps are as follows :
- Initialize ‘prev0’ and ‘prev1’ equal to 1, they will store the count of binary strings ending at the previous index and having 0-bit and 1-bit respectively as their ending bits. Also declare variables ‘cur0’ and ‘cur1’.
- Run a FOR loop for variable ‘i’ from 2 to N, inside the loop:
- Update ‘cur0’ equal to prev0 + prev1.
- Update ‘cur1’ equal to prev0.
- Now, store ‘cur0’ in ‘prev0’ and store ‘cur1’ in ‘prev1’.
- Finally, return the sum of ‘cur0’ and ‘cur1’.
- Initialize a variable ‘ans’ equal to sum cur0 and cur1, this will store the final count of binary strings that don’t contain consecutive 1’s, which is also equal to the number of ways of building electric poles on one side of the road.
- Finally return the square of ‘ans’, to also take into account the other side of the road.