Count of distinct N | Function to find the count of distinct arrays of size n having elements in range [ 1 , k ] and all adjacent elements ( P , Q ) follows ( P <= Q ) or ( P % Q > 0 ) ; Stores the divisors of all integers in the range [ 1 , k ] ; Calculate the divisors of all integers using the Sieve ; Stores the dp states such that dp [ i ] [ j ] with i elements having j as the last element of array ; Initialize the dp array ; Calculate the dp states using the derived relation ; Calculate the sum for len - 1 ; Subtract dp [ len - 1 ] [ j ] for each factor of j from [ 1 , K ] ; Calculate the final result ; Return the resultant sum ; Driver Code
def countArrays ( n , k ) : NEW_LINE INDENT divisors = [ [ ] for i in range ( k + 1 ) ] NEW_LINE for i in range ( 1 , k + 1 , 1 ) : NEW_LINE INDENT for j in range ( 2 * i , k + 1 , i ) : NEW_LINE INDENT divisors [ j ] . append ( i ) NEW_LINE DEDENT DEDENT dp = [ [ 0 for i in range ( k + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for j in range ( 1 , k + 1 , 1 ) : NEW_LINE INDENT dp [ 1 ] [ j ] = 1 NEW_LINE DEDENT for x in range ( 2 , n + 1 , 1 ) : NEW_LINE INDENT sum = 0 NEW_LINE for j in range ( 1 , k + 1 , 1 ) : NEW_LINE INDENT sum += dp [ x - 1 ] [ j ] NEW_LINE DEDENT for y in range ( 1 , k + 1 , 1 ) : NEW_LINE INDENT dp [ x ] [ y ] = sum NEW_LINE for d in divisors [ y ] : NEW_LINE INDENT dp [ x ] [ y ] = ( dp [ x ] [ y ] - dp [ x - 1 ] [ d ] ) NEW_LINE DEDENT DEDENT DEDENT sum = 0 NEW_LINE for j in range ( 1 , k + 1 , 1 ) : NEW_LINE INDENT sum += dp [ n ] [ j ] NEW_LINE DEDENT return sum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 2 NEW_LINE K = 3 NEW_LINE print ( countArrays ( N , K ) ) NEW_LINE DEDENT