Count of distinct N | Java program of the above approach ; 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
import java . util . * ; class GFG { static int countArrays ( int n , int k ) { Vector < Integer > [ ] divisors = new Vector [ k + 1 ] ; for ( int i = 0 ; i < divisors . length ; i ++ ) divisors [ i ] = new Vector < Integer > ( ) ; for ( int i = 1 ; i <= k ; i ++ ) { for ( int j = 2 * i ; j <= k ; j += i ) { divisors [ j ] . add ( i ) ; } } int [ ] [ ] dp = new int [ n + 1 ] [ k + 1 ] ; for ( int j = 1 ; j <= k ; j ++ ) { dp [ 1 ] [ j ] = 1 ; } for ( int x = 2 ; x <= n ; x ++ ) { int sum = 0 ; for ( int j = 1 ; j <= k ; j ++ ) { sum += dp [ x - 1 ] [ j ] ; } for ( int y = 1 ; y <= k ; y ++ ) { dp [ x ] [ y ] = sum ; for ( int d : divisors [ y ] ) { dp [ x ] [ y ] = ( dp [ x ] [ y ] - dp [ x - 1 ] [ d ] ) ; } } } int sum = 0 ; for ( int j = 1 ; j <= k ; j ++ ) { sum += dp [ n ] [ j ] ; } return sum ; } public static void main ( String [ ] args ) { int N = 2 , K = 3 ; System . out . print ( countArrays ( N , K ) ) ; } }