• + 0 comments

    This problem required very little memoization. I noticed a pattern; consider the number of arrays of length 2: [0,1,1] where index is the ending number x. Using a dynamic coding strategy, you might try to find the number of arrays of length 3 by summing up elements of this array: [2,1,1] You don't add the number of arrays of length 2 ending in the same x, since the numbers can't appear twice in a row. Therefore, index 1 is one greater, since it ignored the one element that was 1 less than the others. Using this array, the number of arrays of length 4 is: [2,3,3] This time, index 1 is one less since it ignored the one element that was one more than the rest. The pattern continues: [6,5,5] [10,11,11]

    So we can ditch using arrays and just consider the number of arrays ending in x>1. The number N(n) of arrays of length n ending in x>1 is equal to (k-1)*N(n-1) + (1 if n is even, -1 if n is odd)

    if x==1, subtract 1 if n is even, add 1 if n is odd

    function countArray(n: number, k: number, x: number): number {
        // Return the number of ways to fill in the array.
        //ending in number col+1
        //array of length row+2
        //NOTE: for EVEN length, there is one less array ending in 1. for ODD, there is one extra.
        // Otherwise, the number of constructable arrays of length n ending in k is equal to the sum of all arrays of length n-1, + or - one depending on n's parity.
        let curr = 1;
        
        let mod = (Math.pow(10,9)+7)
        
        let even;
        let odd;
        //iterate over possible lengths
        for(let i=2; i<n; i++)
        {
            even = i%2
            odd = even==1?0:1
            //add even bonus, remove odd
            curr = (curr*(k-1) + even - odd) % mod
        }
        if(x==1) curr += (-even + odd)
        
        return curr
    }