Problem

Given a positive integer N, count all distinct binary strings of length N that do not contain two consecutive 1 bits.

Examples

Example 1

1
2
3

Input: N = 2
Output: 3
Explanation: the strings are `00`, `01`, `10`.

Example 2

1
2
3

Input: N = 3
Output: 5
Explanation: the strings are `000`, `001`, `010`, `100`, `101`.
Similar Problems

Solution

This problem is a classic two-state dynamic programming problem. Let a[i] be the number of valid strings of length i that end with 0, and let b[i] be the number that end with 1.

Method 1 — Two-state DP (iterative)

Intuition

If a valid string of length i ends with 0, the previous bit can be 0 or 1 (both valid). If it ends with 1, the previous bit must be 0 to avoid consecutive 1s. Therefore a[i] depends on both a[i-1] and b[i-1], while b[i] depends only on a[i-1].

Approach

  • Initialize a[1] = 1 and b[1] = 1 (strings 0 and 1).
  • For i from 2 to N:
    • a[i] = a[i-1] + b[i-1] (append 0 to any valid length i-1 string)
    • b[i] = a[i-1] (append 1 only to strings that ended with 0)
  • The total count for length N is a[N] + b[N].
  • Edge cases: if N <= 0, return 0; if N == 1, return 2.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
 public:
  long long countNoConsecOnes(int N) {
    if (N <= 0) return 0;
    long long a = 1;  // ends with 0
    long long b = 1;  // ends with 1
    for (int i = 2; i <= N; ++i) {
      long long na = a + b;
      long long nb = a;
      a = na;
      b = nb;
    }
    return a + b;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

package main

func countNoConsecOnes(N int) int64 {
    if N <= 0 {
        return 0
    }
    var a int64 = 1
    var b int64 = 1
    for i := 2; i <= N; i++ {
        na := a + b
        nb := a
        a = na
        b = nb
    }
    return a + b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public long countNoConsecOnes(int N) {
    if (N <= 0) return 0;
    long a = 1; // ends with 0
    long b = 1; // ends with 1
    for (int i = 2; i <= N; ++i) {
      long na = a + b;
      long nb = a;
      a = na;
      b = nb;
    }
    return a + b;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def count_no_consec_ones(self, N: int) -> int:
        if N <= 0:
            return 0
        a: int = 1  # ends with 0
        b: int = 1  # ends with 1
        for _ in range(2, N + 1):
            na = a + b
            nb = a
            a = na
            b = nb
        return a + b

Complexity

  • ⏰ Time complexity: O(N), we iterate N-1 times updating two counters.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.

Method 2 — Fibonacci relation and fast exponentiation

Intuition

The total count for length N follows Fibonacci numbers: count(N) = fib(N+2). This is visible by expanding the DP: total(N) = a[N] + b[N] = a[N] + a[N-1] and a[N] = total(N-1), which yields the Fibonacci recurrence.

Approach

  • Use the identity count(N) = F_{N+2} where F_k is the k-th Fibonacci number (with F_0 = 0, F_1 = 1).
  • Compute F_{N+2} using fast doubling / matrix exponentiation to achieve O(log N) time.
  • Edge cases: handle N <= 0.

Code (fast doubling Fibonacci)

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
 public:
  // returns pair (F(n), F(n+1))
  std::pair<long long, long long> fibPair(long long n) {
    if (n == 0) return {0, 1};
    auto p = fibPair(n >> 1);
    long long a = p.first;
    long long b = p.second;
    long long c = a * (2 * b - a);
    long long d = a * a + b * b;
    if (n & 1) return {d, c + d};
    else return {c, d};
  }

  long long countNoConsecOnesFast(long long N) {
    if (N <= 0) return 0;
    return fibPair(N + 2).first;
  }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

package main

func fibPair(n int64) (int64, int64) {
    if n == 0 {
        return 0, 1
    }
    a, b := fibPair(n >> 1)
    c := a * (2*b - a)
    d := a*a + b*b
    if n&1 == 1 {
        return d, c + d
    }
    return c, d
}

func countNoConsecOnesFast(N int64) int64 {
    if N <= 0 {
        return 0
    }
    f, _ := fibPair(N + 2)
    return f
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  private long[] fibPair(long n) {
    if (n == 0) return new long[]{0, 1};
    long[] p = fibPair(n >> 1);
    long a = p[0], b = p[1];
    long c = a * (2*b - a);
    long d = a*a + b*b;
    if ((n & 1) == 1) return new long[]{d, c + d};
    else return new long[]{c, d};
  }

  public long countNoConsecOnesFast(long N) {
    if (N <= 0) return 0;
    return fibPair(N + 2)[0];
  }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def fib_pair(self, n: int) -> tuple[int, int]:
        if n == 0:
            return 0, 1
        a, b = self.fib_pair(n >> 1)
        c = a * (2*b - a)
        d = a*a + b*b
        if n & 1:
            return d, c + d
        return c, d

    def count_no_consec_ones_fast(self, N: int) -> int:
        if N <= 0:
            return 0
        return self.fib_pair(N + 2)[0]

Complexity

  • ⏰ Time complexity: O(log N) using fast doubling (or matrix exponentiation).
  • 🧺 Space complexity: O(log N) due to recursion depth (iterative matrix exponentiation can reduce this to O(1)).

References

  • Original explanation and sample implementation: GeeksforGeeks (moved to source_links).
  • MIT old quiz solution (moved to source_links).