Count of N | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; map < int , int > dp ; int countStrings ( int N ) { if ( N == 1 ) return 0 ; if ( dp . find ( N ) != dp . end ( ) ) return dp [ N ] ; int ret = 0 ; for ( int div = 1 ; div <= sqrt ( N ) ; div ++ ) { if ( N % div == 0 ) { ret += ( 1 << div ) - countStrings ( div ) ; int div2 = N / div ; if ( div2 != div and div != 1 ) ret += ( 1 << div2 ) - countStrings ( div2 ) ; } } dp [ N ] = ret ; return ret ; } int main ( ) { int N = 6 ; cout << countStrings ( N ) << endl ; }