Build Electric Poles

Moderate
0/80
profile
Contributed by
1 upvote
Asked in company
PayU

Problem statement

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?
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
2
Sample Output 1 :
64
9
Explanation For Sample Input 1 :
For test case 1 :
We will print 64 because:
There are 64 possible arrangements to build the electric poles when we have four plots on each side of the road.

For test case 2 : 
We will print 9 because:
There are 9 possible arrangements to build the electric poles when we have four plots on each side of the road.
If “| |” represents the road, “#” represents an empty plot, and “^” represents an electric pole. Then all the possible arrangements are:
1) # # | | # #
2) # # | | # ^
3) # ^ | | # ^
4) ^ # | | # ^
5) # # | | ^ #
6) # ^ | | ^ #
7) ^ # | | ^ #
8) # ^ | | # #
9) ^ # | | # #
Sample Input 2 :
2
10
100
Sample Output 2 :
20736
20522904
Hint

Find some symmetry and think of a brute force recursive approach.

Approaches (3)
Recursion

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 :

  1. Initialize a variable ‘ans’ equal to 0, this variable stores the final answer.
  2. 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’.
  3. 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.
  4. Finally return the square of ‘ans’, to also take into account the other side of the road.
Time Complexity

O( 2 ^ N ), where N denotes the length of the binary string.

 

To calculate the current position we are making two recursive calls to the previous position, this leads to an exponential time complexity (consider the number of nodes in a binary tree of height equal to ‘N’ for reference).

Hence the time complexity is O( 2^N ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Build Electric Poles
Full screen
Console