Count of arrays in which all adjacent elements are such that one of them divide the another | Javascript program to count number of arrays of size n such that every element is in range [ 1 , m ] and adjacen are divisible ; For storing factors . ; For storing multiples . ; Calculating the factors and multiples of elements [ 1. . . m ] . ; Initialising for size 1 array for each i <= m . ; Calculating the number of array possible of size i and starting with j . ; For all previous possible values . Adding number of factors . ; Adding number of multiple . ; Calculating the total count of array which start from [ 1. . . m ] . ; Driver Code
let MAX = 1000 ; function numofArray ( n , m ) { let dp = new Array ( MAX ) ; let di = new Array ( MAX ) ; let mu = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) { dp [ i ] = new Array ( MAX ) ; for ( let j = 0 ; j < MAX ; j ++ ) { dp [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i < MAX ; i ++ ) { di [ i ] = [ ] ; mu [ i ] = [ ] ; } for ( let i = 1 ; i <= m ; i ++ ) { for ( let j = 2 * i ; j <= m ; j += i ) { di [ j ] . push ( i ) ; mu [ i ] . push ( j ) ; } di [ i ] . push ( i ) ; } for ( let i = 1 ; i <= m ; i ++ ) dp [ 1 ] [ i ] = 1 ; for ( let i = 2 ; i <= n ; i ++ ) { for ( let j = 1 ; j <= m ; j ++ ) { dp [ i ] [ j ] = 0 ; for ( let x = 0 ; x < di [ j ] . length ; x ++ ) dp [ i ] [ j ] += dp [ i - 1 ] [ di [ j ] [ x ] ] ; for ( let x = 0 ; x < mu [ j ] . length ; x ++ ) dp [ i ] [ j ] += dp [ i - 1 ] [ mu [ j ] [ x ] ] ; } } let ans = 0 ; for ( let i = 1 ; i <= m ; i ++ ) { ans += dp [ n ] [ i ] ; di [ i ] = [ ] ; mu [ i ] = [ ] ; } return ans ; } let n = 3 , m = 3 ; document . write ( numofArray ( n , m ) ) ;