We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Construct the Array
  5. Discussions

Construct the Array

  • 221dwj
     + 1 comment

    An O(n) Python3 solution:

    def countArray(n, k, x):
    # Note:
    # The key point to achieve linear time complexity is to realize that all x where x!=1 are symmetrical.
    # So instead of iterate over a table of size n*k, we only need to iterate over a table of size n*2
    
    table = []

    table.append([0,0]) # The first list in table is arbitrary. It won't be used
    table.append([0,1]) 
    for i in range(2, n):
        table.append([-1,-1])

    for i in range(2, n):
        # If the i-th element is 1, then all k-1 possibilities for (i-1)-th element are symmetrical. 
        table[i][0] = (k-1)*table[i-1][1] % int(1e9+7)
        
        # If the i-th element is not 1, then we have k-2 symmetrical possibilities for (i-1)-th element, plus the case where (i-1)-th element is 1.
        table[i][1] = (table[i-1][0] + (k-2)*table[i-1][1]) % int(1e9+7)
         
    if x == 1:
        return table[n-1][0] % int(1e9+7)
    else:
        return table[n-1][1] % int(1e9+7)