Given an integer K, we have to construct an array of length N in such a way that, first element is always 1 and last element is always X, another integer given as input. Each element in the array must be [1, K] and the adjacent elements must not be the same. We have to find out the number of ways to construct such arrays.

Example: N = 4 K = 3 X = 2 ans = 3 Possible arrays: [1, 2, 3, 2] [1, 2, 1, 2] [1, 3, 1, 2]

Solution

We can try to visualise the construction of the array in the form of a tree.

Consider the tree below for the above example: At each level, we branch out to form a possible valid array value. The blue circles, represent the array ending that are equal to X, thus valid and the green ones are invalid.

Let a be the array to represent in the number of valid arrays of length i and b represent the number of invalid arrays of length i. We can derive the following overlapping subproblems in the problem.

1. a[i] = b[i-1] This makes sense as, if we can make M arrays of length i-1 that are invalid then the same number of arrays can be made of length i that are valid. Just append the valid number at the end.

2. b[i] = (a[i-1] * (k-1)) + (b[i-1] * (k-2)) First part says, if the last number was a valid array ending, then we have k-1 numbers to use. Second part says, if the last number was one of the invalid numbers, then we have k-2 numbers to use, 1 invalid and 1 valid numbers have to be subtracted.