8

The problem is to find the number of repeatable binary strings of length n.A binary string is repeatable if it can be obtained by any sub string of the binary string that repeats itself to form the original binary string.

Example
"1010" is a repeatable string as it can be obtained from "10" by repeating 2 number of times

"1001" is  not a repeatable string as it cannot be obtained from any sub string of "1001" by repeating them any number of times

The solution I thought of is to generate all possible binary string of length n and check whether it is is a repeatable or not using KMP algorithm, but this solution is not feasible even for small n like n=40.

The second approach I thought is

  1. for divisor k of n find all sub strings of length k that repeats itself n/k times

Example for n = 6 we have divisor 1,2,3

for length 1 we have 2 sub string "1" and "0" that repeats itself 6 times so "111111" and "000000" are repeatable strings

for length 2 we have 4 sub strings "00" "01" "10" "11" so "000000" "010101" "101010" and "111111" are repeatable strings

similarly for length 3 we have 8 strings that are repeatable.

  1. Sum up all the divisor generated string and subtract duplicates.

In the above example the string "111111" and "000000" was counted 3 times for each of the divisor.so clearly I am over counting.I need to subtract duplicates but I can't think of anyway to subtract duplicates from my actual count How can I do that?

Am I headed in the right direction or do I need to any other approach?

1
  • 1
    Your current approach looks good to me. To figure out how to avoid counting strings twice, it would be a good idea to look at (e.g. the Wikipedia article for) the Inclusion-Exclusion Principle. Apr 18, 2016 at 20:12

2 Answers 2

1

When you use the second scheme remove the sub strings which made of repeatable binaries. For instance, 00 and 11 are made of the repeat of 0 and 1 respectively. So for length of 2 only consider the "01" and "10" for length of 3 only consider "001", "010", "011", "100", "101", "110" ... generally, for odd length of n remove 0 and (2^n)-1, for even length of n, remove 0, (2^(n/2)+1), (2^(n/2)+1)2, ...., (2^n)-1 and if n dividable by 3, (1+2^(n/2)+2^(n-2)), (1+2^(n/2)+2^(n-2)) 2, ... continue this for all divider.

0

One idea is that if we only count the ways to make the divisor-sized strings from non-repeated substrings, the counts from the divisors's divisors will account for the ways to make the divisors from repeated substrings.

f(1) = 0
f(n) = sum(2^d - f(d)), where 1 <= d < n and d divides n

...meaning the sum of only the ways divisors of n can be made not from repeated substrings.

f(2) = 2^1-0
f(3) = 2^1-0
f(4) = 2^1-0 + 2^2-2
f(6) = 2^1-0 + 2^2-2 + 2^3-2
...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.