Count the number of binary strings without consecutive 1’s

Starting from a given length, find all the possible distinct binary strings of that length, in such a way that there are no consecutive ones.

​Input: int length = 3; Output: 5 Explanation: The strings are: 000, 001, 010, 100, 101.

Solution:

1. static int countBinaryStrings(int length) { 2. int[] endingIn0 = new int[length]; 3. int[] endingIn1 = new int[length]; 4. endingIn0[0] = endingIn1[0] = 1; 5. for (int i = 1; i < length; i++) { 6. endingIn0[i] = endingIn0[i - 1] + endingIn1[i - 1]; 7. endingIn1[i] = endingIn0[i - 1]; 8. } 9. return endingIn0[length - 1] + endingIn1[length - 1]; 10. } 11.