Problem Link - Periodic Strings
Problem Statement -
A string is any nonempty sequence of 0s and 1s. Examples of strings are 00, 101, 111000, 1, 0, 01. The length of a string is the number of symbols in it. For example, the length of 111000 is 6. If u and v are strings, then uv is the string obtained by concatenating u and v. For example if u = 110 and v = 0010 then uv = 1100010.
A string w is periodic if there exists a string v such that w = vn = vv · · · v (n times), for some n ≥ 2. Note that in this case the length of v is strictly less than that of w. For example, 110110 is periodic, because it is vv for v = 110.
Given a positive integer N , find the number of strings of length N which are not periodic. Report the answer modulo M . The non-periodic strings of length 2 are 10 and 01. The non- periodic strings of length 3 are 001, 010, 011, 100, 101, and 110.
Approach
To solve the problem, first calculate the total number of binary strings of length N, which is 2^N. Next, count the periodic strings of length N using their divisors. A string of length N is periodic if it can be formed by repeating a smaller substring of length d, where d is a divisor of N. Using dynamic programming, calculate the number of strings of length i that are periodic by iterating over its divisors. Subtract these periodic counts from the total to get the count of non-periodic strings. Modular arithmetic ensures calculations remain within bounds of M.
Time Complexity
The time complexity is O(N^2), as we iterate over divisors for each i up to N.
Space Complexity
The space complexity is O(N), as we use arrays of size N+1 for computations.