For more clear picture please refer -->http://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+14 votes

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

The value of $x_5$ is

- $5$
- $7$
- $8$
- $16$

0

+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!

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

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.

+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

x2=3

x3=5

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

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

so ans will be 13

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

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.

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 568
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,515 questions

52,763 answers

183,377 comments

68,235 users