Count of N | Store the recurring recursive states ; Function to find the number of strings of length N such that it is a concatenation it substrings ; Single character cant be repeated ; Check if this state has been already calculated ; Stores the resultant count for the current recursive calls ; Iterate over all divisors ; Non - Repeated = Total - Repeated ; Non - Repeated = Total - Repeated ; Store the result for the further calculation ; Return resultant count ; Driver code ; Function Call
let dp = new Map ( ) ; function countStrings ( N ) { if ( N == 1 ) return 0 ; if ( dp . has ( N ) ) return dp . get ( N ) ; let ret = 0 ; for ( let div = 1 ; div <= Math . sqrt ( N ) ; div ++ ) { if ( N % div == 0 ) { ret += ( 1 << div ) - countStrings ( div ) ; let div2 = N / div ; if ( div2 != div && div != 1 ) ret += ( 1 << div2 ) - countStrings ( div2 ) ; } } dp [ N ] = ret ; return ret ; } let N = 6 ; document . write ( countStrings ( N ) + " " ) ;