Count possible ways to construct buildings

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
public class Solution {
    public int possibleWays(int n) {
        if (n == 1)
            return 2;
        int buildWays = 1, dontBuildWays = 1;
        // Only consider for 1 side
        for (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 side
        return (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
}

Last updated