Count of valid arrays of size P with elements in range [ 1 , N ] having duplicates at least M distance apart | Function to calculate the total number of arrays ; If the size of the array is P ; Check if all elements are used atlease once ; Check if this state is already calculated ; Initialize the result ; Use a number from the list of unused numbers ; There are ' unused ' number of favourable choices ; Use a number from already present number atlease M distance back ; There are ' used ▁ - ▁ M ' number of favourable choices ; Store the result ; Function to solve the problem ; Initialize DP table : dp [ i ] [ j ] [ j ] i : current position / index j : number of used elements k : number of unused elements ; Driver Code
function calculate ( position , used , unused , P , M , dp ) { if ( position == P ) { return unused == 0 ? 1 : 0 ; } if ( dp [ position ] [ used ] [ unused ] != - 1 ) return dp [ position ] [ used ] [ unused ] ; let result = 0 ; if ( unused > 0 ) { result += calculate ( position + 1 , used + 1 , unused - 1 , P , M , dp ) * unused ; } if ( used > M ) { result += calculate ( position + 1 , used , unused , P , M , dp ) * ( used - M ) ; } return dp [ position ] [ used ] [ unused ] = result ; } function solve ( N , P , M ) { var dp = new Array ( 101 ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( 101 ) . fill ( - 1 ) ; } for ( let i = 0 ; i < dp . length ; i ++ ) { for ( let j = 0 ; j < dp [ 0 ] . length ; j ++ ) { dp [ i ] [ j ] = new Array ( 101 ) . fill ( - 1 ) ; } } return calculate ( 0 , 0 , N , P , M , dp ) ; } let N = 2 , M = 0 , P = 3 ; document . write ( solve ( N , P , M ) ) ;