Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1’s.
Examples:
Input: N = 2 Output: 3 // The 3 strings are 00, 01, 10 Input: N = 3 Output: 5 // The 5 strings are 000, 001, 010, 100, 101
Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.
PHP
<?php// PHP program to count all distinct// binary stringswithout two// consecutive 1'sfunction countStrings($n){ $a[$n] = 0; $b[$n] = 0; $a[0] = $b[0] = 1; for ($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];} // Driver Code echo countStrings(3) ;// This code is contributed by nitin mittal?> |
Output:
5
Time Complexity: O(n)
Auxiliary Space: O(n)
Please refer complete article on Count number of binary strings without consecutive 1’s for more details!
<!–
–>
Php Program to Count 1’s in a sorted binary array
Php Program to check if strings are rotations of each other or not
PHP Program to Count trailing zeroes in factorial of a number
PHP Program to Find the Number Occurring Odd Number of Times
Php Program to Check whether all the rotations of a given number is greater than or equal to the given number or not
Php Program for Counting sets of 1s and 0s in a binary matrix
Php Program to Check horizontal and vertical symmetry in binary matrix
How to trim all strings in an array in PHP ?
PHP Program to Count set bits in an integer
PHP Program for Count ways to reach the n\’th stair
Article Contributed By :
neveropen
Vote for difficulty
Improved By :
Article Tags :
Please Login to comment…