Count of arrays in which all adjacent elements are such that one of them divide the another | Java 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
import java . util . * ; class GFG { static int MAX = 1000 ; static int numofArray ( int n , int m ) { int [ ] [ ] dp = new int [ MAX ] [ MAX ] ; Vector < Integer > [ ] di = new Vector [ MAX ] ; Vector < Integer > [ ] mu = new Vector [ MAX ] ; for ( int i = 0 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) { dp [ i ] [ j ] = 0 ; } } for ( int i = 0 ; i < MAX ; i ++ ) { di [ i ] = new Vector < > ( ) ; mu [ i ] = new Vector < > ( ) ; } for ( int i = 1 ; i <= m ; i ++ ) { for ( int j = 2 * i ; j <= m ; j += i ) { di [ j ] . add ( i ) ; mu [ i ] . add ( j ) ; } di [ i ] . add ( i ) ; } for ( int i = 1 ; i <= m ; i ++ ) dp [ 1 ] [ i ] = 1 ; for ( int i = 2 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= m ; j ++ ) { dp [ i ] [ j ] = 0 ; for ( Integer x : di [ j ] ) dp [ i ] [ j ] += dp [ i - 1 ] [ x ] ; for ( Integer x : mu [ j ] ) dp [ i ] [ j ] += dp [ i - 1 ] [ x ] ; } } int ans = 0 ; for ( int i = 1 ; i <= m ; i ++ ) { ans += dp [ n ] [ i ] ; di [ i ] . clear ( ) ; mu [ i ] . clear ( ) ; } return ans ; } public static void main ( String [ ] args ) { int n = 3 , m = 3 ; System . out . println ( numofArray ( n , m ) ) ; } }