The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
897 views

Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive 0s.

The value of $x_5$ is 

  1. $5$
  2. $7$
  3. $8$
  4. $16$
asked in Algorithms by Veteran (116k points)
edited by | 897 views
0

4 Answers

+14 votes
Best answer

Number of binary strings of length n that contain no consecutive 0s, following will be the required recurrence relation:

$T(n) = T(n-1) + T(n-2)$    $n>2$
base condition $T(1) = 2$   and $T(2) = 3$

$T(1) =2$                       There will be $ 2$ strings of length $1$, i.e $0\ \& \ 1$
$T(2) =3  $                       There will be $3$ strings of length $2$, i.e. $01,10,11$
$T(3) = T(1) + T(2) = 2+3 = 5$
$T(4) = T(3) + T(2) = 5 + 3 = 8$
$T(5) = T(4) +T(3) = 8 + 5 = 13$

Hence, answer is 13, but no option matches!

answered by Boss (17.3k points)
edited by
+1
Question copied from rosen ..
+5
They do it from standard books - still most aspirants are allergic to standard books :)
+9 votes
Here X1 =0,1(2)

X2=01,10,11(total 3)

X3=010,011,101,110,111(total 5)

Here X3=X2+x1

X4=3+5=8

X5=5+8=13

No option matching here.
answered by Boss (38.8k points)
+2 votes
x1=2

x2=3

x3=5

x4=8.................... so on

it seems fibbonacci form so x5=5+8=13

 so ans will be 13
answered by Active (4.3k points)
+1 vote
Though everyone has already given the correct answer but let me try an easier explanation.

You can do it by hit and trial method.

The smallest string you can think of in the first attempt is

Let's say x1, then it should contain either 0 or 1.

So, for x1 Answer = 2

for x2, it may contain, 11, 10 or 01 ----------> = 3

Similarly, for x3 it may contain, 111, 110, 101, 011, 010 ---------------> = 5

Now, you can see that it is forming a series like 2, 3, 5, ....and so on.

Recall, this popular series. It's nothing but the Fibonacci series.

So, here's your answer for.

since, f(n) = f(n-1) + f(n-2), (By fibonacci Series)

So, f(5) = f(4) + f(3), ...............(1)

f(4) = f(3) + f(2) = 5 + 3...........(2)

putting this value of equation 2 in equation 1.

f(5) = 8 + 5

So, answer = 13.
answered by Active (3.4k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,427 questions
53,611 answers
185,916 comments
70,885 users