public static long countArray(int n, int k, int x) { long mode = 1000000000 + 7; long[][] dp = new long[n + 1][2]; if (n == 2) { if (x == 1) return 0; else return 1; } if (x != 1) { dp[2][0] = 1; dp[2][1] = k - 2; } else { dp[2][0] = 0; dp[2][1] = k - 1; } for (int i = 3; i <= n; i++) { dp[i][0] = dp[i - 1][1] % mode; dp[i][1] = (dp[i - 1][1] * (k - 2) + dp[i - 1][0] * (k - 1)) % mode; }

    return dp[n][0];
}

I don't know where this code is wrong. I modularized it, but the answer is different.

static long mod(long x){
    while(x<0)
        x+=1000000007;
    return (x%1000000007);    
}
public static long countArray(int n, int k, int x)
{
// Return the number of ways to fill in the array.
    if(k<=1 || n<2)return 0;
    if(k==2 && n<=3) return 0;
    if(k==2)
    {
        if(x==1 ) 
        {
            if( n%2==0)  return 0;
            return 1;
        }
        if(x==2)
        {
            if( n%2==1)  return 0;
            return 1;
        }
    }

    long result= 1;
    int N=n-2;

    for(int i=0;i<N;i++)
    {
        result = mod(result*(k-1));
    }
    //result=mod(result*k);
    Console.WriteLine("result : "+result);
    long kn=1;
    for(int i=0;i<N-1;i++)
    {
        kn = mod(kn*(k-1));
    }
    Console.WriteLine("kn : "+kn);
    //result=mod(result-2*kn);
    Console.WriteLine("result : "+result);
    long ss1=0;
    long ss2=0;

        ss1 =mod(((kn+(k-1)*(((N-1)%2==0)?1:-1))/k));
        ss2 =mod(((kn+(((N)%2==0)?1:-1))/k));
    if(x==1)
    {
        kn=mod(ss2*(k-1));
    Console.WriteLine("ss1 : "+kn);
    }
    else 
    {
        kn=mod(ss2*(k-2)+ss1);
    Console.WriteLine("ss2 : "+kn);
    }
    return mod(result -kn);
}

For an O(n) time and O(1) space complexity, we can think of this problem as keeping track of the total combinations depending on whether we placed an X value previously or we didn't (from n = 3 to n - 2). At n = 2, we either had [1,X] or [1, not X and not 1] if X != 1, or [1,1] and [1, not 1] if X = 1; this gives us combinations of 1 and (k - 2) respectively for the X != 1 case, and 0 and (k - 1) respectively for the X = 1 case. For the iterations from 3 to n - 2, we need to update the “previous was not X” and the “previous was X” combination values. If the previous value was not X, we have two choices: place an X or don’t. If we place an X, the total combinations have not changed, therefore the new “previous was X” is just the previous “previous was not X” value. If we don’t place an X and the previous was not X, the new “previous was not X” combinations are multiplied by (k-2), since we can’t place the previous number either. Finally, we have the case where the previous was X and we don’t place an X. There are (k-1) options, so we multiply the “previous was X” value by (k-1) and add it to the new “previous was not X” value. At n - 1 position, we can never place an X. So if the n - 2 spot was an X, we have (k-1) options and if not, we have (k-2) options. Therefore, our final result will be: “previous was X” times (k-1) + “previous was not X” times (k-2). Not dynamic programming really, but intuitively makes sense. See Java solution below.

public static long countArray(int n, int k, int x) {
        // Base Cases
        if (n == 3) {
           return (1 == x) ? k - 1 : k - 2;
        }
        if (k == 2) {
            if (1 == x) {
                return (n % 2);
            } else {
                return (n % 2 == 0) ? 1 : 0;
            }
        }
        int mod = 1000000007;
        if (n == 4) {
            if (1 == x) {
                return ((k - 1) % mod) * ((k - 2) % mod);
            } else {
                return (k-1) + ((k-2) % mod)* ((k-2) % mod);
            }
        }
        // start at position 3 and go until 2 before n
        long prevWasX;
        long prevWasNotX;
        if (1 == x) {
            prevWasNotX = k - 1;
            prevWasX = 0;
        } else {
            prevWasNotX = k - 2;
            prevWasX = 1;
        }
        // start at position 3 and go until 2 before n
        for (int i = 3; i <= n-2; i++) {
            long newPrevWasX;
            long newPrevNotX;
            // If previous was X, can place anything but X
            newPrevNotX = ((prevWasX % mod) * (k-1)) % mod;
            
            // If previous was not X, can place X or not place X
            // Do not place X or previous
            newPrevNotX += ((prevWasNotX % mod) * (k-2)) % mod;
            
            // Place X, if previous not X
            newPrevWasX = prevWasNotX % mod;
            
            // Update Counts
            prevWasNotX = newPrevNotX;
            prevWasX = newPrevWasX;
        }
        // Last Spot (before X)
        // If previous was X, can place anything but X
        long lastSpot1= ((prevWasX % mod) * (k - 1)) % mod;
        
        // If previous was not X, can place anything but X and previous
        long lastSpot2 = ((prevWasNotX % mod) * (k - 2)) % mod;
        
        return (lastSpot1 + lastSpot2) % mod;
    }

Hello,

For me the same solution is passing in python but failing in Scala, can someone help me debug it?

    if((n-2)%2==1):
        y=((((k-1)**(n-2-1))-1))//k
        if (x == 1):
            ways = ((y + 1)*(k-1))+((((k-1)*y))*(k-2))
        else:
            ways=((((k-1)*y) + 1)*(k-2))+((y)*(k-1))
    else:
        y = ((((k - 1) ** (n - 2 - 1)) + 1)) // k
        if (x == 1):
            ways = ((y - 1)*(k-1))+(((k-1)*y)*(k-2))
        else:
            ways=((((k-1)*y) - 1)*(k-2))+((y)*(k-1))

    if (n % 2 == 1) {
      val y = (scala.math.pow(k - 1, n - 3).toLong - 1) / k
      if (x == 1) {
        ((y + 1) * (k - 1)) + ((k - 1) * y * (k - 2))
      }
      else {
        ((((k - 1) * y) + 1) * (k - 2)) + (y * (k - 1))
      }
    }
    else {
      val y = (scala.math.pow(k - 1, n - 3).toLong + 1) / k
      if (x == 1) {
        ((y - 1) * (k - 1)) + ((k - 1) * y * (k - 2))
      }
      else {
        ((((k - 1) * y) - 1) * (k - 2)) + (y * (k - 1))
      }

    } % div

JAVA: --> public static final int MOD = 1000000007; static long[][] memo; static int x, n, k;

     public static long dp(int u, int isX) {
    if (u == n - 1) return isX == 1 ? 1 : 0;
    if (memo[u][isX] != -1) return memo[u][isX];
    long ans = 0;
    if (isX == 1 || (u == 0 && x == 1)) {
        ans += (k - 1) * dp(u + 1, 0);
    } else {
        ans += (k - 2) * dp(u + 1, 0);
        ans %= MOD;
        ans += dp(u + 1, 1);
    }
    ans %= MOD;
    return memo[u][isX] = ans;
}

public static long countArray(int n, int k, int x) {
    Result.n = n;
    Result.k = k;
    Result.x = x;
    memo = new long[n][2];
    for (int i = 0; i < n; i++)
        Arrays.fill(memo[i], -1);
    return dp(0, 0) % MOD;

}