CODEWITHSUNDEEP
stringalgorithmcombinatoricscounting
Prashant Bhanarkar
Prashant Bhanarkar

Reputation: 960

count the number of binary string of length n that is repeatable

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?

Upvotes: 8

Views: 1050

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

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
...

Upvotes: 0

Hoda
Hoda

Reputation: 63

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.

Upvotes: 1

Related Questions