Given a positive integer N, the task is to find the number of binary strings of length N that are repeated concatenation of only one substring of that string.
Examples:
Input: N = 4
Output: 4
Explanation:
Below are the possible binary string of length N(= 4):
- “0000”: This string is the repeated concatenation of the substring “0”.
- “1111”: This string is the repeated concatenation of the substring “1”.
- “0101”: This string is the repeated concatenation of the substring “01”.
- “1010”: This string is the repeated concatenation of the substring “10”.
Therefore, the total count of such string is 4. Hence, print 4.
Input: N = 10
Output: 34
Approach: The given problem can be solved based on the observation that every possible string has a repeated substring which concatenated say K times, then the given length of string N must be divisible by K to generate all the resultant string.
Therefore, find all possible divisors of N and for each divisor, say K find the count of all possible strings it can form whose concatenation is the resultant string and this count can be calculated by 2K. Now, the number of strings that are repeated among them must also be subtracted, So perform the same operation on the divisor K and subtract it from 2K to get the total count for each recursive call.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Store the recurring recursive states map<int, int> dp;// Function to find the number of// strings of length N such that it// is a concatenation it substringsint countStrings(int N){ // Single character cant be repeated if (N == 1) return 0; // Check if this state has been // already calculated if (dp.find(N) != dp.end()) return dp[N]; // Stores the resultant count for // the current recursive calls int ret = 0; // Iterate over all divisors for(int div = 1; div <= sqrt(N); div++) { if (N % div == 0) { // Non-Repeated = Total - Repeated ret += (1 << div) - countStrings(div); int div2 = N/div; if (div2 != div and div != 1) // Non-Repeated = Total - Repeated ret += (1 << div2) - countStrings(div2); } } // Store the result for the // further calculation dp[N] = ret; // Return resultant count return ret;}// Driver codeint main(){ int N = 6; // Function Call cout << countStrings(N) << endl;}// This code is contributed by ipg2016107 |
Java
// Java program for the above approachimport java.util.*;class GFG{// Store the recurring recursive states static HashMap<Integer, Integer> dp = new HashMap<Integer, Integer>();// Function to find the number of// strings of length N such that it// is a concatenation it substringsstatic int countStrings(int N){ // Single character cant be repeated if (N == 1) return 0; // Check if this state has been // already calculated if (dp.containsKey(N)) return dp.get(N); // Stores the resultant count for // the current recursive calls int ret = 0; // Iterate over all divisors for(int div = 1; div <= Math.sqrt(N); div++) { if (N % div == 0) { // Non-Repeated = Total - Repeated ret += (1 << div) - countStrings(div); int div2 = N / div; if (div2 != div && div != 1) // Non-Repeated = Total - Repeated ret += (1 << div2) - countStrings(div2); } } // Store the result for the // further calculation dp.put(N, ret); // Return resultant count return ret;}// Driver Codepublic static void main(String[] args){ int N = 6; // Function Call System.out.print(countStrings(N));}}// This code is contributed by code_hunt |
Python3
# Python program for the above approach# Store the recurring recursive states dp = {}# Function to find the number of# strings of length N such that it# is a concatenation it substringsdef countStrings(N): # Single character cant be repeated if N == 1: return 0 # Check if this state has been # already calculated if dp.get(N, -1) != -1: return dp[N] # Stores the resultant count for # the current recursive calls ret = 0 # Iterate over all divisors for div in range(1, int(N**.5)+1): if N % div == 0: # Non-Repeated = Total - Repeated ret += (1 << div) - countStrings(div) div2 = N//div if div2 != div and div != 1: # Non-Repeated = Total - Repeated ret += (1 << div2) - countStrings(div2) # Store the result for the # further calculation dp[N] = ret # Return resultant count return ret# Driver CodeN = 6# Function Callprint(countStrings(N)) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Store the recurring recursive states static Dictionary<int, int> dp = new Dictionary<int, int>();// Function to find the number of// strings of length N such that it// is a concatenation it substringsstatic int countStrings(int N){ // Single character cant be repeated if (N == 1) return 0; // Check if this state has been // already calculated if (dp.ContainsKey(N)) return dp[N]; // Stores the resultant count for // the current recursive calls int ret = 0; // Iterate over all divisors for(int div = 1; div <= Math.Sqrt(N); div++) { if (N % div == 0) { // Non-Repeated = Total - Repeated ret += (1 << div) - countStrings(div); int div2 = N / div; if (div2 != div && div != 1) // Non-Repeated = Total - Repeated ret += (1 << div2) - countStrings(div2); } } // Store the result for the // further calculation dp[N] = ret; // Return resultant count return ret;}// Driver Codepublic static void Main(){ int N = 6; // Function Call Console.Write(countStrings(N));}}// This code is contributed by splevel62. |
Javascript
<script>// JavaScript program for the above approach// Store the recurring recursive stateslet dp = new Map();// Function to find the number of// strings of length N such that it// is a concatenation it substringsfunction countStrings(N) { // Single character cant be repeated if (N == 1) return 0; // Check if this state has been // already calculated if (dp.has(N)) return dp.get(N); // Stores the resultant count for // the current recursive calls let ret = 0; // Iterate over all divisors for (let div = 1; div <= Math.sqrt(N); div++) { if (N % div == 0) { // Non-Repeated = Total - Repeated ret += (1 << div) - countStrings(div); let div2 = N / div; if (div2 != div && div != 1) // Non-Repeated = Total - Repeated ret += (1 << div2) - countStrings(div2); } } // Store the result for the // further calculation dp[N] = ret; // Return resultant count return ret;}// Driver codelet N = 6;// Function Calldocument.write(countStrings(N) + "<br>");// This code is contributed by _saurabh_jaiswal</script> |
Output:
10
Time Complexity: O(N)
Auxiliary Space: O(N)
Another approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better than Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a DP of size N+1 to store the solution of the subproblems.
- Initialize the DP with base cases dp[0] = 1.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- Return the final solution stored in dp[N]
Implementation :
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to find the number of// strings of length N such that it// is a concatenation it substringsint countStrings(int N){ // Single character cant be repeated if (N == 1) return 0; // initialize DP vector<int> dp(N+1); // Base case dp[1] = 0; // Iterate over subproblems to compute current // value from previous computations for (int i = 2; i <= N; i++) { int ret = 0; for(int div = 1; div <= sqrt(i); div++) { if (i % div == 0) { ret += (1 << div) - dp[div]; int div2 = i/div; if (div2 != div and div != 1) ret += (1 << div2) - dp[div2]; } } // update dp dp[i] = ret; } // return final answer return dp[N];}// Driver codeint main(){ int N = 6; // Function Call cout << countStrings(N) << endl;} // this code is contributed by bhardwajji |
Java
import java.util.*;public class Main { // Function to find the number of // strings of length N such that it // is a concatenation it substrings static int countStrings(int N) { // Single character cant be repeated if (N == 1) return 0; // initialize DP int[] dp = new int[N + 1]; // Base case dp[1] = 0; // Iterate over subproblems to compute current // value from previous computations for (int i = 2; i <= N; i++) { int ret = 0; for (int div = 1; div <= Math.sqrt(i); div++) { if (i % div == 0) { ret += (1 << div) - dp[div]; int div2 = i / div; if (div2 != div && div != 1) ret += (1 << div2) - dp[div2]; } } // update dp dp[i] = ret; } // return final answer return dp[N]; } // Driver code public static void main(String[] args) { int N = 6; // Function Call System.out.println(countStrings(N)); }}//This code is contributed by Akash Jha |
Python
# Python program for the above approachimport math# Function to find the number of# strings of length N such that it# is a concatenation it substringsdef countStrings(N): # Single character cant be repeated if N == 1: return 0 # initialize DP dp = [0]*(N+1) # Base case dp[1] = 0 # Iterate over subproblems to compute current # value from previous computations for i in range(2, N+1): ret = 0 for div in range(1, int(math.sqrt(i))+1): if i % div == 0: ret += (1 << div) - dp[div] div2 = i // div if div2 != div and div != 1: ret += (1 << div2) - dp[div2] # update dp dp[i] = ret # return final answer return dp[N]# Driver codeif __name__ == '__main__': N = 6 # Function Call print(countStrings(N)) |
C#
using System;public class Program{ // Function to find the number of // strings of length N such that it // is a concatenation it substrings static int CountStrings(int N) { // Single character cant be repeated if (N == 1) return 0; // initialize DP int[] dp = new int[N + 1]; // Base case dp[1] = 0; // Iterate over subproblems to compute current // value from previous computations for (int i = 2; i <= N; i++) { int ret = 0; for (int div = 1; div <= Math.Sqrt(i); div++) { if (i % div == 0) { ret += (1 << div) - dp[div]; int div2 = i / div; if (div2 != div && div != 1) ret += (1 << div2) - dp[div2]; } } // update dp dp[i] = ret; } // return final answer return dp[N]; } // Driver code public static void Main() { int N = 6; // Function Call Console.WriteLine(CountStrings(N)); }}//This code is contributed by Akash Jha |
Javascript
// Function to find the number of// strings of length N such that it// is a concatenation it substringsfunction countStrings(N) { // Single character cant be repeated if (N == 1) { return 0; } // initialize DP let dp = new Array(N + 1); // Base case dp[1] = 0; // Iterate over subproblems to compute current // value from previous computations for (let i = 2; i <= N; i++) { let ret = 0; for (let div = 1; div <= Math.sqrt(i); div++) { if (i % div == 0) { ret += (1 << div) - dp[div]; let div2 = i / div; if (div2 != div && div != 1) { ret += (1 << div2) - dp[div2]; } } } // update dp dp[i] = ret; } // return final answer return dp[N];}// Driver codelet N = 6;// Function Callconsole.log(countStrings(N)); |
Output:
10
Time Complexity: O(N * sqrt(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
