Given a number N, find the number of binary strings of length N that contains consecutive 1's in them.
 
Example 1:
Input:
N = 2
Output:
1
Explanation:
There are 4 strings of 
length 2, the strings 
are 00, 01, 10, and 
11. Only the string 11 
has consecutive 1's.
 
 
Example 2:
Input:
N = 5
Output:
19
Explanation:
There are 19 strings
having consecutive 1's.
 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function numberOfConsecutiveOnes() which takes an integer N and returns the number of binary strings that contain consecutive 1's in them.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
 
Constraints
2 <= N <=30

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3

class Solution:

    def numberOfConsecutiveOnes (ob,N):

        # code here 

        

Solutions:
class Solution:

	def numberOfConsecutiveOnes(ob, N):
		(x, a, b) = (1, 0, 0)
		for i in range(N - 1):
			c = x + a + b
			(x, a, b) = (x << 1, c, a)
		return c


import math

class Solution:

	def numberOfConsecutiveOnes(ob, N):
		a = [0 for i in range(N)]
		b = [0 for i in range(N)]
		a[0] = b[0] = 1
		for i in range(1, N):
			a[i] = a[i - 1] + b[i - 1]
			b[i] = a[i - 1]
		nonConsucative = a[N - 1] + b[N - 1]
		totalStrings = math.pow(2, N)
		return int(totalStrings - nonConsucative)


class Solution:

	def numberOfConsecutiveOnes(ob, N):
		dp1 = [0] * N
		dp2 = [0] * N
		dp1[0] = dp2[0] = 1
		for i in range(1, N):
			dp1[i] = dp2[i - 1]
			dp2[i] = dp1[i - 1] + dp2[i - 1]
		return (1 << N) - dp1[N - 1] - dp2[N - 1]


class Solution:

	def numberOfConsecutiveOnes(ob, n):
		a = [0 for i in range(n)]
		b = [0 for i in range(n)]
		a[0] = b[0] = 1
		for i in range(1, n):
			a[i] = a[i - 1] + b[i - 1]
			b[i] = a[i - 1]
		return (1 << n) - (a[n - 1] + b[n - 1])


class Solution:

	def numberOfConsecutiveOnes(ob, N):
		MOD = 10 ** 9 + 7
		a = [0 for i in range(N)]
		b = [0 for i in range(N)]
		a[0] = b[0] = 1
		for i in range(1, N):
			a[i] = (a[i - 1] % MOD + b[i - 1] % MOD) % MOD
			b[i] = a[i - 1] % MOD
		return 2 ** N - (a[N - 1] % MOD + b[N - 1] % MOD) % MOD


class Solution:

	def numberOfConsecutiveOnes(ob, n):
		(a, b) = (3, 5)
		if n == 2:
			return 1
		if n == 3:
			return 3
		for i in range(4, n + 1):
			(a, b) = (b, a + b)
		ans = 2 ** n - b
		return ans


class Solution:

	def numberOfConsecutiveOnes(ob, N):
		fib = [0] * (N + 2)
		(fib[0], fib[1]) = (1, 1)
		for i in range(2, N + 2):
			fib[i] = fib[i - 1] + fib[i - 2]
		return (1 << N) - fib[N + 1]


class Solution:

	def numberOfConsecutiveOnes(ob, N):
		A = [0] * N
		B = [0] * N
		A[0] = 1
		B[0] = 1
		for i in range(1, N):
			A[i] = A[i - 1] + B[i - 1]
			B[i] = A[i - 1]
		C = A[N - 1] + B[N - 1]
		return (1 << N) - C


class Solution:

	def numberOfConsecutiveOnes(ob, N):
		dp = [0, 0, 1]
		fib = [0, 1]
		for i in range(2, N):
			u = fib[-1] + fib[-2]
			dp.append(dp[-1] * 2 + u)
			fib.append(u)
		return dp[-1]


class Solution:

	def numberOfConsecutiveOnes(ob, N):
		A = [0] * N
		B = [0] * N
		A[0] = 1
		B[0] = 1
		for i in range(1, N):
			A[i] = A[i - 1] + B[i - 1]
			B[i] = A[i - 1]
		C = A[N - 1] + B[N - 1]
		return (1 << N) - C
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.numberOfConsecutiveOnes(N))


class Solution:

	def numberOfConsecutiveOnes(ob, N):
		a = (0, 0)
		b = (1, 1)
		for j in range(3, N + 1):
			c1 = 2 * b[0]
			c2 = b[1] + a[1]
			a = b
			b = (c1 + c2, c2)
		return b[0]


class Solution:

	def numberOfConsecutiveOnes(ob, N):
		if N == 0 or N == 1:
			return 0
		dpEnd0 = [0 for i in range(N + 1)]
		dpEnd1 = [0 for i in range(N + 1)]
		dpEnd0[1] = 1
		dpEnd1[1] = 1
		ans = 0
		for i in range(2, N + 1):
			dpEnd1[i] = dpEnd0[i - 1]
			dpEnd0[i] = dpEnd0[i - 1] + dpEnd1[i - 1]
		return 2 ** N - (dpEnd1[N] + dpEnd0[N])


class Solution:

	def numberOfConsecutiveOnes(ob, n):
		dpend1 = [0] * n
		dpend0 = [0] * n
		dpend1[0] = 1
		dpend0[0] = 1
		for i in range(1, n):
			dpend1[i] = dpend0[i - 1]
			dpend0[i] = dpend0[i - 1] + dpend1[i - 1]
		return 2 ** n - (dpend0[n - 1] + dpend1[n - 1])


class Solution:

	def numberOfConsecutiveOnes(ob, n):
		dp0 = [0] * (n + 1)
		dp1 = [0] * (n + 1)
		dp0[1] = 1
		dp1[1] = 1
		for i in range(2, n + 1):
			dp0[i] = dp1[i - 1]
			dp1[i] = dp0[i - 1] + dp1[i - 1]
		mod = 10 ** 9 + 7
		return 2 ** n - (dp0[n] + dp1[n]) % mod


class Solution:

	def numberOfConsecutiveOnes(self, N):
		if N == 1:
			return 0
		if N == 2:
			return 1
		p1 = 1
		p2 = 0
		for n in range(3, N + 1):
			w = p1 + p2 + 2 ** (n - 2)
			p2 = p1
			p1 = w
		return w