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.
defcountArray(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*2table=[]table.append([0,0])#Thefirstlistintableisarbitrary.Itwon'tbeusedtable.append([0,1])foriinrange(2,n):table.append([-1,-1])foriinrange(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)ifx==1:returntable[n-1][0]%int(1e9+7)else:returntable[n-1][1]%int(1e9+7)
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 →
An O(n) Python3 solution: