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.
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
functioncountArray(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.letcurr=1;letmod=(Math.pow(10,9)+7)leteven;letodd;//iterate over possible lengthsfor(leti=2;i<n;i++){even=i%2odd=even==1?0:1//add even bonus, remove oddcurr=(curr*(k-1)+even-odd)%mod}if(x==1)curr+=(-even+odd)returncurr}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Construct the Array
You are viewing a single comment's thread. Return to all 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