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
function countArrays ( n , k ) { let divisors = new Array ( k + 1 ) . fill ( new Array ( ) ) ; for ( let i = 1 ; i <= k ; i ++ ) { for ( let j = 2 * i ; j <= k ; j += i ) { divisors [ j ] . push ( i ) ; } } let dp = new Array ( n + 1 ) . fill ( new Array ( k + 1 ) ) ; for ( let j = 1 ; j <= k ; j ++ ) { dp [ 1 ] [ j ] = 1 ; } for ( let x = 2 ; x <= n ; x ++ ) { let sum = 0 ; for ( let j = 1 ; j <= k ; j ++ ) { sum += dp [ x - 1 ] [ j ] ; } for ( let y = 1 ; y <= k ; y ++ ) { dp [ x ] [ y ] = sum ; for ( let d of divisors [ y ] ) { dp [ x ] [ y ] = ( dp [ x ] [ y ] - dp [ x - 1 ] [ d ] ) ; } } } let sum = 0 ; for ( let j = 1 ; j <= k ; j ++ ) { sum += dp [ n ] [ j ] ; } sum ++ ; return sum ; } let N = 2 , K = 3 ; document . write ( countArrays ( N , K ) ) ;