Number of binary numbers given constraints on consecutive elements

I've been trying to solve this question for quite a while, given to us by our discrete maths professor. I've been having a hard time in general with it, so I thought I tried looking it up online but couldn't find anything much useful. Any help will be appreicatted in solving this.

A binary string consists of ones and zeros. Ram tells you number of occurences of 00, 01, 10, and 11 respectively in the string. Come up with an algorithm assuming those values to be variables to find the number of such possible strings. Note that if the number of occurences of 11,10,00, and 01 are 1, 1, 2, 1 respectively, you can come up with 5 such binary strings that satisfy it.

I did come up with a recursive formulation for this, that is f(p, q, r, s) where those are the variables respectively. From a theoretical CS perspective, it would take $O(2*p*q*r*s)$ time to compute. Our professor has specifically told it can be done better, just I dont know how better.

• Before "looking it up online", did you check that the last sentence is true? – leonbloy Jan 29 '16 at 18:57
• @leonbloy sorry I mis-typed the order. It's 11,10,00, and 01 => (1, 1, 2, 1). The strings will be 110001,100011,011000,001100,000110 – Play Boy Jan 29 '16 at 18:59
• @PlayBoy: Hi, and welcome to MSE! – Eli Rose Jan 29 '16 at 19:00
• Ongoing competition: hackerrank.com/contests/worldcodesprint/challenges/… Such a coincidence that your professor gave this problem just during the competition :-). Has he gave any other questions from the competition? – Salvador Dali Jan 30 '16 at 12:11
• @DanielFischer unfortunately you have to register there to be able to see a list of problems. The problem there was absolutely the same as posted here (even the example with 1, 1, 2, 1). Right now the competition finished, and everyone can see the solutions, so this guy is surely no longer interested in the solution :-). – Salvador Dali Jan 30 '16 at 21:30

1 Answer

If we draw a directed multigraph with two nodes, 0 and 1, and draw $p$ edges from 1 to 1, $q$ edges from 1 to 0, etc.

                   q
___   ------>  ___
--\ /   \ /        /   \/--
p |   |  1  |        |  0  |  | r
--> \___/ <------/ \___/<--
s


then the number of such strings is the number of different paths that visit every edge in the graph. (Actually, it's twice that number, since you can start at $0$ or at $1$).

I'm not sure if this can be converted into a more efficient algorithm than already given, however.

• If I'm not wrong this is essentially the same thing as the recursion. Do you know of anything more efficient? – Play Boy Jan 29 '16 at 19:24
• You are not wrong, and I do not know of anything more efficient. – Eli Rose Jan 29 '16 at 19:25