Given an input number of sections and each section has 2 plots on either sides of the road. Find all possible ways to construct buildings in the plots such that there is a space between any 2 buildings.
Example :
N = 1
Output = 4
Place a building on one side.
Place a building on other side
Do not place any building.
Place a building on both sides.
N = 3
Output = 25
3 sections, which means possible ways for one side are
BSS, BSB, SSS, SBS, SSB where B represents a building
and S represents an empty space
Total possible ways are 25, because a way to place on
one side can correspond to any of 5 ways on other side.
N = 4
Output = 64
publicclassSolution {publicintpossibleWays(int n) {if (n ==1)return2;int buildWays =1, dontBuildWays =1;// Only consider for 1 sidefor (int i =2; i <= n; i++) {int temp = buildWays; buildWays = dontBuildWays; dontBuildWays = temp + dontBuildWays; }// Ans -> Number of ways for 1 side * Number of ways for 1 sidereturn (buildWays + dontBuildWays) * (buildWays + dontBuildWays); }// We can also notice that answer for nth is fib(n)^2// therefore we can solve it in O(logN) using power method}