Here is the solution of Construct the Array Click Here

There is a closed form solution that's the sum of a geometric alternating series, and does not require dynamic programming.

Here's the hint: count the number of ways you can construct ALL possible arrays starting from 1, disregarding the x at the end. Then, subtract out the number that end in x.

Since the array starts with 1, at each step the number of ways that end in 1 will be different from the number of ways that end in 2..k

For example, on the first step, we will have (k-1) possible values, and all will be in the range 2..k

Then on the 2nd step, we have (k-1)^2 possible combinations. (k-1) will be 1 and (k-1)^2 - (k - 1) will be in the range 2..k

On the 3rd step, (k-1)^3 total possible combinations. (k-1)^2 - (k-1) are 1, and (k-1)^3 - (k-1)^2 + (k-1) will be 2..k

This gives you an alternating geometric series that you can either compute sequentially in O(n), or find the closed form for and compute in O(log n) (to compute (k-1)^n)

Best possible solution can be done using a dp array of size 2 * 2 :)

Here is problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-construct-the-array-problem-solution.html

I was wondering why can't i solve this using combinations from itertools? Anyone who can find flaws in this approach?

from itertools import combinations
def countArray(n, k, x):
    if x==1:
        return 1
    c=list(combinations(range(k),n-2))
    print(c)
    return len(c)%((10^9)+7)