What is Count Number of Binary Strings without Consecutive 1’s?

Let's consider an example to explain the concept of counting binary strings without consecutive 1's.

Example

Suppose we want to count the number of binary strings of length 3 that do not contain consecutive 1's. A binary string is a string consisting of only 0's and 1's.

The possible binary strings of length 3 are: 000, 001, 010, 011, 100, 101, 110, and 111.

However, we need to count only those binary strings that do not have consecutive 1's. So, we need to exclude the strings 011, 101, and 111 from the count.

Let's analyse the remaining binary strings:

• 000: This is a valid string because it doesn't have consecutive 1's.

• 001: This is a valid string because it doesn't have consecutive 1's.

• 010: This is a valid string because it doesn't have consecutive 1's.

• 100: This is a valid string because it doesn't have consecutive 1's.

• 110: This is an invalid string because it has consecutive 1's.

From the above analysis, we can see that there are 4 valid binary strings of length 3 without consecutive 1's.

PHP Program to Count Number of Binary Strings without Consecutive 1's

Method 1- Using Dynamic Programming

Example

Output

Number of binary strings without consecutive 1's: 13

Explanation of code

This PHP code defines a function called countBinaryStrings that calculates the number of binary strings of length $n without consecutive 1's using dynamic programming. It initializes an array $dp with the base cases $dp[0] = 1 and $dp[1] = 2, representing the counts for strings of length 0 and 1, respectively. It then uses a loop to fill in the remaining counts for lengths 2 to $n, by summing the counts for lengths $i - 1 and $i - 2. Finally, it returns the count for length $n and prints it. In this specific example, the code calculates the number of binary strings without consecutive 1's for a length of 5 and displays the result.

Method 2

Output

Number of binary strings without consecutive 1's: 13

Explanation of code

This PHP code calculates the number of distinct binary strings of length $n without two consecutive 1's. It defines two arrays, $a and $b, to store the counts. The base cases are set as $a[0] = $b[0] = 1. Then, a loop is used to calculate the counts for lengths 1 to $n-1. The count for length $i is obtained by summing the count for length $i-1 from array $a and the count for length $i-1 from array $b. Additionally, the count for length $i in array $b is obtained from the count for length $i-1 in array $a. Finally, the code returns the sum of the count for length $n-1 from array $a and the count for length $n-1 from array $b, representing the total count of binary strings without consecutive 1's. In this particular example, the code calculates the count for a length of 5 and displays the result.

Conclusion

In conclusion, the first method utilizes dynamic programming, initializing an array with base cases and iteratively calculating the counts for larger lengths. It efficiently computes the result by summing the counts for the previous two lengths. The second method employs a simpler approach, using two arrays to store counts and iteratively updating them based on the counts from the previous length. It directly calculates the total count without the need for summing the two arrays separately. Both methods provide accurate counts for binary strings without consecutive 1's, and the choice between them may depend on specific requirements and performance considerations.