CODEWITHSUNDEEP
puzzle
Chander Shivdasani
Chander Shivdasani

Reputation: 10121

Number of possible binary strings of length k

One of my friends was asked this question recently:

You have to count how many binary strings are possible of length "K". Constraint: Every 0 has a 1 in its immediate left.

Upvotes: 1

Views: 3744

Answers (2)

dvvrd
dvvrd

Reputation: 1689

This question can be reworded: How many binary sequences of length K are posible if there are no two consecutive 0s, but the first element should be 1 (else the constrains fails). Let us forget about the first element (we can do it bcause it is always fixed). Then we got a very famous task that sounds like this: "What is the number of binary sequences of length K-1 that have no consecutive 0's." The explanation can be found, for example, here

Then the answer will be F(K+1) where F(K) is the K`th fibonacci number starting from (1 1 2 ...).

Upvotes: 2

Musa
Musa

Reputation: 97672

∑ From n=0 to ⌊K/2⌋ of (K-n)Cn; n is the number of zeros in the string

The idea is to group every 0 with a 1 and find the number of combinations of the string, for n zeros there will be n ones grouped to them so the string becomes (k-n) elements long. There can be no more than of K/2 zeros as there would not have enough ones to be to the immediate left of each zero.
E.g. 111111[10][10]1[10] for K = 13, n = 3

Upvotes: 0

Related Questions