Count of N | Java program for the above approach ; 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
import java . util . * ; class GFG { static HashMap < Integer , Integer > dp = new HashMap < Integer , Integer > ( ) ; static int countStrings ( int N ) { if ( N == 1 ) return 0 ; if ( dp . containsKey ( N ) ) return dp . get ( N ) ; int ret = 0 ; for ( int div = 1 ; div <= Math . sqrt ( N ) ; div ++ ) { if ( N % div == 0 ) { ret += ( 1 << div ) - countStrings ( div ) ; int div2 = N / div ; if ( div2 != div && div != 1 ) ret += ( 1 << div2 ) - countStrings ( div2 ) ; } } dp . put ( N , ret ) ; return ret ; } public static void main ( String [ ] args ) { int N = 6 ; System . out . print ( countStrings ( N ) ) ; } }