Google interview question | Glass and color distribution count

Problem statement :

Given two color Red and Green, in how many ways you can fill ‘N’ glasses with these colors with below condition.

1. You can’t fill 3 glass conjugatively with the same color, which means you can fill conjugatively two glass with the same color but 3rd glass must have to be a different color.

An example is given n=3

The possible ways will be (R for Red and G for Green)

RGG, RGR, RRG, GGR, GRG, GRR that is 6 ways

when n=4, the output will be 10

Solution : You can fill one glass or two glass with the same color. To fill the ’N’ number of glass we will have two case

1. You are at n-2 glass then fill the reaming glass with the same color
2. You are at n-1 glass then fill the last glass with one color.

So here the base case will be

when n=1, f(1) = 1 *2 ( As there are two colors)

when n=2 f(2) =2 * 2

With the same formula f(n)= f(n-1)+ f(n-2) and then multiply the result by 2, as we have two color.

Recursive Implementation

public static int countWays(int n) {
        return f(n)*2;
    }
    public static int f(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        else
            return (f(n - 1) + f(n - 2));
    }

The same can be done with dynamic programming with O(n) complexity.

public static int dp(int n) {
        int[] s = new int[n];
        s[0] = 1;
        s[1] = 2;
        for (int i = 2; i < n; ++i) {
            s[i] = s[i - 1] + s[i - 2];
        }
        return s[n - 1]*2;
    }