Saturday, April 30, 2016

Count strings with consecutive 1's - GeeksforGeeks

Count strings with consecutive 1's - GeeksforGeeks
Given a number n, count number of n length strings with consecutive 1's in them.
Examples:
`Input  : n = 2  Output : 1  There are 4 strings of length 2, `
`the  strings are 00, 01, 10 and 11. Only the   string 11 has consecutive 1's.  `

1) Compute number of binary strings without consecutive 1’s using the approach discussed here. Let this count be c.
2) Count of all possible binary strings with consecutive 1’s is 2^n where n is input length.
3) Total binary strings with consecutive 1 is 2^n – c.
`int` `countStrings(``int` `n)`
`{`
`    ``// Count binary strings without consecutive 1's.`
`    ``// See the approach discussed on be`
`    ``// ( http://goo.gl/p8A3sW )`
`    ``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];`
`    ``}`

`    ``// Subtract a[n-1]+b[n-1] from 2^n`
`    ``return` `(1<<n) - a[n-1] - b[n-1];`
`}`

Time complexity of above solution is O(n). We can optimize above solution to work in O(Logn).
If we take a closer look at the pattern of counting strings without consecutive 1’s, we can observe that the count is actually (n+2)’th Fibonacci number for n >= 1. The Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ….
```n = 1, count = 0  = 21 - fib(3)
n = 2, count = 1  = 22 - fib(4)
n = 3, count = 3  = 23 - fib(5)
n = 4, count = 8  = 24 - fib(6)
n = 5, count = 19 = 24 - fib(7)
................
```
We can find n’th Fibonacci Number in O(Log n) time (See method 4 here).