Stop worrying about the holes in the road and celebrate the journey.
~ Fitzhugh Mullan
Arrange Buildings
Welcome Back Readers!
We hope that you understand the topic, "Dynamic Programming''. Like always we advise you to practise more and more problems. Now moving to the next problem that is "Arrange Buildings". Prerequisites for this problem is previous problem which was "Count Binary Strings''
If you have already solved that problem then you will be able to grasp this one easily. You are also advised to try to solve that problem before you move to the solution.
And if you haven't solved it yet then I advise you to solve that first. You can find both the problems on our website.
Let's solve the problem.
Problem Discussion :
Suppose you are given a number n, which represents the length of a road. The road has n plots on each side. The road is to be so planned that there should not be consecutive buildings on either side of the road.
You are required to find and print the number of ways in which the buildings can be built on both sides of roads.
For example:
Sample Input: 3
Sample Output: 25
How 25?
We have a total of 5 ways in which buildings can be arranged on a road with 3 plots, without any consecutive buildings and therefore 25 ways to arrange on both sides of the road.
Approach :
Just like in previous problem;
Let's assume two arrays, with n+1 length. Both these arrays will store the count of appropriate plans of road of length i at ith index but one stores the count of roads ending with Building and another ones ending with an empty plot.
Suppose n = 4, let's take a look at both the arrays with corresponding value of count at ith index of i length of road.
In this figure, when length of string is 0, then there will be 0 appropriate plans with no consecutives buildings. When at index 1, there will be 1 plan in each array of length1 that is either a building can be there or not (that is an empty plot).
Now, when at index = 2, if we construct a building at the end of the road which we found at last index in dps[] then we will get all plans of length 2 ending with a building at 2nd index of dpb[]. And similarly if we leave the plot empty at the end of strings which we found at the last index in dpb[] and dps[]then we will get all plans of length 2 ending with an empty plot at 2nd index of dps[] with no consecutive buildings.
As we move forward, we fill our array with same logic, which we generalize as:
dpb[i] = dps[i-1]
dps[i] = dpb[i-1] +dps[i-1]
You can see all the possible strings and count at any index in figure.
Plans ending with an empty plot contribute to both the array as after leaving a plot empty it will be no problem if we construct a building or not, it remains harmless and does not violate conditions of consecutive buildings.
But plans ending with a building contribute to only dps[] array as after leaving the plot empty it does not violate conditions of consecutive buildings. If we would add it's contribution to dpb[], then we are placing two adjacent buildings which is not possible.
Let's try to code this.
Yes! That looks good. But we can still make it better. How?
Instead of using 2 arrays of n length, we can simply use two variables, one(ob, old building) keeping the count of plans ending with buildings and another (os, old space) keeping the count of plans ending with an empty plot, both initialized to 1. And then applying the for loop from 2 to n and defining two variables inside for loop, nb (new building) and ns (new spaces) representing new and updated values of ob and os with similar logic that we used above.
int nb = os;
int ns = os + ob;
Let's code this one.
You can also watch part of the solution video. Taking care of the constraints, we will use long in our code instead of int.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
long n = scn.nextInt();
long ob = 1;
long os = 1;
for(int i = 2; i <= n; i++){
long nb = os;
long ns = os + ob;
ob = nb;
os = ns;
}
int total = ob + os;
System.out.println(total*total);
}
}
java;
true";
Analysis
Time Complexity :
The time complexity of this procedure is O(n) where n is the length of an array.
SPACE COMPLEXITY :
Since we have used two integer variables which take constant space, instead of two arrays of size n + 1, hence we are able to reduce the space complexity from O(n ) to O(1) also we have not used any extra memory or any extra data structure.
We hope that this article was helpful. You must check out our solution video for more clear understanding.
Don't feel stressed out if you are not able to solve any problem at once.
Forgive yourself and stay focused. Until then keep solving and learning new problems on Dynamic Programming.
