Binary strings with no two adjacent ones

Question

Count the length-n binary strings that contain no two consecutive 1s. For n = 2 the valid strings are 00, 01, 10, so the answer is 3. Find the recurrence, explain the exponential naive count, and give an O(n) solution.

Accepted Answer

Split by the last character. A valid string of length n either ends in 0 (the first n-1 characters are any valid string of length n-1) or ends in 1 (which forces the character before it to be 0, so the first n-1 characters form a valid string of length n-1 ending in 0, equivalently a valid length n-2 string followed by 0). That gives a(n) = a(n-1) + a(n-2), \quad a(0) = 1, \ a(1) = 2. Fibonacci again, so a(n) = fib(n+2). A recursion that recomputes a(n-1) and a(n-2) independently branches exponentially over the same handful of distinct subproblems. Roll two values instead: Trace countnoadjace…

Binary strings with no two adjacent ones

Your answer

More Coding questions