Find the number of binary strings of length 10 with no two consecutive 1s.
This problem is shared by Minimario M.
Details and assumptions
A binary string is a sequence of integers that are 1 or 0 . The length of a string refers to the number of integers in it.
As an explicit example, the binary string of length 3 are 0 0 0 , 0 0 1 , 0 1 0 , 0 1 1 , 1 0 0 , 1 0 1 , 1 1 0 , 1 1 1 .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Just an observation: When we count for small cases, starting from binary strings of length 1, we find that the number of strings with no two consecutive 1's is 2. For length = 2, the number of strings with no two consecutive 1's is 3. Similarly, for length = 3, we get 5. Proceeding up to length = 10, the number of strings with no two consecutive 1's for each case are: 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. The Fibonacci pattern.
great! Thx for sharing!!!
What I did was listed it out. I feel stupid.
Log in to reply
Yeah, same, except a program listed them out for me.
Maybe next time, I should change the 10 into a larger number ._.
@below, note that mathematics = data structures and algorithms
Amazing
Consider the last digit of a n -digit bit string.
If it is a 1, then the 2nd to last digit must be a 0, and the string is just a ( n − 2 ) digit bit string with 0 1 attached at the end of it.
If it is a 0, then the string is a ( n − 1 ) digit bit string with 0 attached to the end of it.
Note that these 2 cases will not overlap and will count everything.
Therefore, we obtain a recursion.
Let S n be the number of strings of length n .
Creary, S 1 = 2 and S 2 = 3 .
Therefore, S 3 = 5 , S 4 = 8 , S 5 = 1 3 , S 6 = 2 1 , S 7 = 3 4 , S 8 = 5 5 , S 9 = 8 9 , and S 1 0 = 1 4 4 . Notice that these are the fibonacci numbers.
same approach!
Wow!!!!!!!
Let f ( n ) be the number of binary strings of length n with no two consecutive 1 s. f ( 0 ) = 1 , and f ( 1 ) = 2 .
Consider n > 1 . If a 1 is added at the beginning of the string, then the next digit must be 0 . That means that the number of strings with length n which start with a 1 is f ( n − 2 ) . If a 0 is added instead, there is no restriction on the next digit; the number of strings with length n which start with a 0 is f ( n − 1 ) .
Putting this together leaves us with the recursive formula: f ( n ) = f ( n − 2 ) + f ( n − 1 ) Which is the same recurrence as the Fibonacci sequence, shifted by two.
Therefore, the answer we want is the 1 2 th Fibonacci number: 1 4 4 .
For the 1s not to be together, you have to have a minimum of 5 0s.
For 5 0s: -0-0-0-0-0- So you can put the 5 1s in the remaining places (represented by hyphens) in 6C5 ways.
For 6 0s: -0-0-0-0-0-0-0- So you can put the 4 1s in the remaining places in 7C4 ways.
Similary for 7, 8, 9 and 10 0s.
Therefore the total is: 6C5 + 7C4 + 8C3 + 9C2 + 10C1 + 11C0 = 144
I forgot 11C0
by listing at least 5 binary numbers without two consecutive 1's we can get the ff:
0001 - 1st binary number without two consecutive 1's
0010 - 2nd
0100 - 3rd
0101 - 4th
1000 - 5th
by noticing the pattern we can get that:
pattern | Original Binary Number
13 8 5 3 2 1 | 32 16 8 4 2 1
0 0 0 0 0 0 | 0 0 0 0 0 0
the sequence is known as the Fibonacci Sequence
in this case:
fib(1) = 1
fib(2) = 2
fib(n) = fib(n-1)+fib(n-2)
Example:
Find the number of binary strings of length 5 with no two consecutive 1's.
the answer would be fib(5+1) which is fib(6) = 13.
since the maximum value of binary number with no 2 consecutive 1's is
"10101" - which has the value (1*8) + (0*5) + (1*3) + (0*2) + (1*1) = 12
and since we have to include "00000" - 12 + 1 = 13
in the given problem to find the number of binary strings of length 10 with no two consecutive 1's.
the answer would be f(10+1) = f(11) = 144.
We can make a table with length of the string compared to the number of them that fit the condition, for the first few lengths (because it is quite easy to count these) to find the pattern of the number of them. Then we just continue this pattern until we reach the length 10.
(Length, Number): (1,2), (2,3), (3,5), (4,8), (5,13)
After these first few terms we see that Number follows the Fibonacci sequence, so we can just continue the Fibonacci until the term that corresponds to length 10.
(Length, Number): (6,21), (7,34), (8,55), (9,89), (10,144)
So the answer is 1 4 4
Let f ( n ) be the number of such binary sequences of length n . Suppose we know the values f ( k ) and f ( k + 1 ) then sequences of length k + 2 either end in a 0 and then have any valid sequence of length k + 1 preceding it, or end 0 1 with any sequence of length k preceding it. These are the only possibilities so f satisfies the recursion relation
f ( n + 2 ) = f ( n ) + f ( n + 1 ) .
We clearly have the initial cases f ( 0 ) = 1 and f ( 1 ) = 2 and from this we can compute f ( 1 0 ) = 1 4 4 .
We consider the sequence to have 10,9,8...5 0s respectively, the sequence can't have less than 5 0s cuz in that case there would be at least 2 1s are next to each other. Now we put the remaining 1s into the 'spaces' between the 0s including the 2 ends, and the number of 'spaces' equal the number of 0s + 1, so we have 10C0 + 10C1 + 9C2 + 8C3 + 7C4 + 6C5 = 144
There can only be at most five ones in the binary string so we have six cases. We imagine the crosses as zeros and the lines between them as ones. For example |xx|xxx|x| translates to 1001000101. If there are five crosses we can choose between six spots to place 1 0 − 5 = 5 lines. We can do that in ( 6 − 5 ) ! × 5 ! 6 ! = 6 ways. Generally, if there are n crosses we can choose between n + 1 spots to place 1 0 − n = 5 lines. We can do that in ( ( n + 1 ) − ( 1 0 − n ) ) ! × ( 1 0 − n ) ! ( n + 1 ) ! ways. We add together the ways to arrange the crosses and lines for 0,1,2,3,4 and 5 crosses (Note 0 ! = 1 ):
( 6 − 5 ) ! × 5 ! 6 ! + ( 7 − 4 ) ! × 4 ! 7 ! + ( 8 − 3 ) ! × 3 ! 8 ! + ( 9 − 2 ) ! × 2 ! 9 ! + ( 1 0 − 1 ) ! × 1 ! 1 0 ! + ( 1 1 − 0 ) ! × 0 ! 1 1 ! = 6 + 3 5 + 5 6 + 3 6 + 1 0 + 1 = 1 4 4
why we have maximum five ones?
Let's say we know the sequences that satisfy the problem for length n - 1 (in this case 9 bits). So the number of strings that satisfy the problem of length n is the sum of:
the number of strings that satisfy the problem of length n - 1(just put 0 at the end)
the number of strings that satisfy the problem of length n - 1 that end with 0 (put 1 at the end)
Since for n = 1 there are 2 possibilities (one ending with 0 and the other with 1) and (letting f(n) denote the number we seek)
f(n) = f(n - 1) + f(n - 2) (if we define f(0) = 1).
So the number of strings is the (n + 1)th fibonacci number given f(0) = 1 and f(1) = 2 f(10 + 1) = f(11) = 144
I found the solution folowing a thinking similar to Ivan Henrique, I think his explanation is the easiest I found. Anyway, the solution is based on Fibonacci numbers
Let B ( n ) be the number of binary strings of length n with no two consecutive 1's.
When n = 1 , there are 2 strings: 0 and 1 , When n = 2 , there are 3 strings: 0 0 , 0 1 , and 1 0 When n = 3 , there are 5 strings: 0 0 0 , 0 0 1 , 0 1 0 , 1 0 1 , and 1 0 0 . When n = 4 , there are 8 strings: 0 0 0 0 , 0 0 0 1 , 0 0 1 0 , 0 1 0 1 , 0 1 0 0 , 1 0 0 0 , 1 0 0 1 , 1 0 1 0 . We notice that B ( 3 ) = B ( 2 ) + B ( 1 ) , and B ( 4 ) = B ( 3 ) + B ( 2 ) For all the binary strings of length j , there exists a binary string of length j + 1 : this is because we can put a 0 before the binary string and ensure that no consecutive 1's are present. This takes care of all binary strings that start with a 0 . For the binary strings that start with 1 , the next digit must be 0 , and we must have a binary string of length j − 2 . This is just B ( j − 2 ) Therefore, B ( j ) is simply equal to B ( j − 1 ) + B ( j − 2 ) . Therefore, B ( 5 ) = B ( 4 ) + B ( 3 ) = 8 + 5 = 1 3 B ( 6 ) = B ( 5 ) + B ( 4 ) = 1 3 + 8 = 2 1 B ( 7 ) = B ( 6 ) + B ( 5 ) = 2 1 + 1 3 = 3 4 B ( 8 ) = B ( 7 ) + B ( 6 ) = 3 4 + 2 1 = 5 5 B ( 9 ) = B ( 8 ) + B ( 7 ) = 5 5 + 3 4 = 8 9 B ( 1 0 ) = B ( 9 ) + B ( 8 ) = 8 9 + 5 5 = 1 4 4
The maximum amount of ones is five, the minimum amount is zero. When there are five ones, we can choose a set of five of six possible spaces. Doing the same analysis the equation is: ( 5 6 ) + ( 4 7 ) + ( 3 8 ) + ( 2 9 ) + ( 1 1 0 ) + 1 = 1 4 4 .
why we have maximum five ones?
Log in to reply
If have more of five ones, will always two consecutive 1s. Sorry for bad english.
it is easy to see that the number of zeroes we can use ranges from 1 0 to 5 .
because we must have at least one zero in between any two consecutive ones. and for the rest of the cases where we have less than 5 zeroes, the number of spaces between the ones is more than the number of zeroes.
case 1 : we have 1 0 zeroes. so 1 for this case.
case 2 : we have 9 zeroes and 1 one.
0 0 0 0 0 0 0 0 0
we have 1 0 places to place that one.
so this case counts for C ( 1 0 , 1 ) = 1 0 .
so we got the trick. we first place the zeroes and then we put the ones.
and when we are using x zeroes, the number of available spaces is x + 1 .
the answer is thus 1 + C ( 1 0 , 1 ) + C ( 9 , 2 ) + C ( 8 , 3 ) + C ( 7 , 4 ) + C ( 6 , 5 ) = 1 4 4
Let Sk be the set of all binary strings of length k with no two consecutive 1s . To obtain binary strings of length k+1 , either append 0 to every string of set Sk or append 0 and then append 1 to every string of set Sk-1 . Hence, n(Sk+1) = n(Sk) + n(Sk-1) . It is a Fibonacci sequence. n(S10) = F(10) with F(1) = 2, F(2) = 3
Basically it is fibonacci series where we can analyze the given question by factoring in the following aspects: Let Sn be the set of binary sequences of length n. Note that |Sn| = 2n.
Let Fn be the set of sequences of binary sequences of length n that do not contain two consecutive 1 bits. The Kata asks us to determine |Fn|. I'll call that f(n).
By inspection, it's easy to work out the first few values of f(n). Note that when n=0, we can count the empty sequence. so here we have a fibonacci series having terms as 1 as f(0),2 as f(1),3 as f(2),5 as f(3),8 as f(4),13 as f(5),21 as f(6),34 as f(7),55 as f(8),89 as f(9),144 as f(10) and hence when n= 10 we can find the value of f(10) through this series which comes out to be 144
At the n t h number of the string, let a n and b n is the number of cases that n t h number is 0 and 1 respectively. If the previous number ( ( n − 1 ) t h number) is 0, so n t h number can be 0 or 1, otherwise, it can be only 0. Therefore:
a n = a n − 1 + b n − 1
b n = a n − 1
And the total number of cases which is also the number of string of length n, is the sum of these two variables:
S n = a n + b n = a n + 1
Apply the above equation, we have:
S n = a n + b n = a n + a n − 1 = S n − 1 + S n − 2
At the first number, there is two cases: 1 and 0, thus S 1 = 2 , a 1 = 1 , b 1 = 1 .
At the 2nd number, S 2 = a 2 + b 2 = S 1 + a 1 = 2 + 1 = 3
At the 3rd number, S 3 = S 2 + S 1 = 2 + 3 = 5
Therefore, at the 10th number, S 1 0 = 1 4 4 and it is also the solution of this problem.
One can see the Fibonacci pattern by writing out the number of possibilities for lengths 1, 2, 3, 4...
length 1 : 0,1
length 2 : 00,01,10
length 3 : 000,001,010,100,101
...
Thus one can see the Fibonacci pattern: 2,3,5,8,13,21,34,55,89, 144 . The answer for a binary string with length 10 is 144
Let start from binary string with length 1, you will get 2 strings. With length 2, you will get 3 strings. With length 3, you will get 5 strings. With length 4, you will get 8 strings. With length 5, you will get 13 strings. With this, we deduce that the number of strings is like fibonacci sequence, where binary string with length n, you will get F n + 2 . Now, we can find how many of binary strings with length 10 = F 1 2 = 1 4 4
Problem Loading...
Note Loading...
Set Loading...
Let the starting digit (1st digit) be 1. (1 possibility for 1st place) In that case the second digit has to be 0. (1 possibility for 2nd place ) So the third digit can be either 0 or 1 (2 possibilities for 3rd place). If the third digit is 1 then the 4th digit has to be 0 & if the third digit is 0 then the 4th digit can be 0 or 1. (3 possibilities for 4th place). Similarly checking corresponding digits for 0 & 1 we get the following: (5 possibilities for 5th place), (8 possibilities for 6th place), (13 possibilities for 7th place), (21 possibilities for 8th place), (34 possibilities for 9th place) & (55 possibilities for 10th place). The possibilities go as in a Fibonacci sequence. So when the starting digit is 1 the number of possibilities is 55. When the starting digit is 0 and the 2nd digit is 1, the last possibility is eliminated & we get 34 choices. When the 1st two starting digits are 0 and the 3rd digit is 1, then the last two possibilities get eliminated & we get 21 choices. Proceeding in this way when the 1st seven digits are zero and the 8th digit is 1, the last seven possibilities get eliminated & we get 2 choices viz 0000000,100; 0000000,101. When the 1st eight digits are zero and the 9th digit is 1, the last eight possibilities get eliminated & we get 1 choice viz 00000000,10. When the 1st nine digits are zero the last nine possibilities get eliminated & we get 1 choice viz 000000000,1. Then there is the last case where all digits are 0's. So ultimately we get 1+1+1+2+3+5+8+13+21+34+55=144 This most probably would seem like an overly complex process but its how I did the sum...