Count number of binary strings without consecutive 1's - GeeksforGeeks
Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1's.
http://www.ideserve.co.in/learn/distinct-binary-strings-of-length-n-with-no-consecutive-1s
Space Optimization:
Count strings without consecutive 1s - PrismoSkills
Read full article from Count number of binary strings without consecutive 1's - GeeksforGeeks
Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1's.
Let a[i] be the number of binary strings of length i which do not contain any two consecutive 1’s and which end in 0. Similarly, let b[i] be the number of such strings which end in 1.
We can append either 0 or 1 to a string ending in 0, but we can only append 0 to a string ending in 1. This yields the recurrence relation:
We can append either 0 or 1 to a string ending in 0, but we can only append 0 to a string ending in 1. This yields the recurrence relation:
a[i] = a[i - 1] + b[i - 1] b[i] = a[i - 1]
The base cases of above recurrence are a[1] = b[1] = 1. The total number of strings of length i is just a[i] + b[i].
int countStrings(int n){ int a[n], b[n]; a[0] = b[0] = 1; for (int i = 1; i < n; i++) { a[i] = a[i-1] + b[i-1]; b[i] = a[i-1]; } return a[n-1] + b[n-1];}Space Optimization:
public static int countBinary(int N) { int C0 = 1; int C1 = 1; for(int i=1; i<N; i++) { int temp = C1; C1 = C0; C0 = C0 + temp; } return C0 + C1; }Read full article from Count number of binary strings without consecutive 1's - GeeksforGeeks
