Count the number of all possible binary strings without consecutive 1’s

You are provided an integers N. You need to count all possible distinct binary strings of length N such that there are no consecutive 1’s.Input Format

First line contains integer t which is number of test case. For each test case, it contains an integer n which is the the length of Binary String.Constraints

1<=t<=100 1<=n<=90Output Format

Print the number of all possible binary strings.Sample Input

2
2
3

Sample Output

3
5

Explanation

1st test case : 00, 01, 10 2nd test case : 000, 001, 010, 100, 101

Solution

import java.util.*;
public class Main {
    public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int t = scan.nextInt();
		while(t-- > 0)
		{
			int n = scan.nextInt();
			long[] a = new long[n];
			long[] b = new long[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];
			}
			System.out.println(a[n-1]+b[n-1]);
		}
    }
}

Code Walkthrough

N = 3


a = {1, 0, 0}
b = {1, 0, 0}

for(int i=1;i<n;i++)
{
  //i = 1

  a[i] = a[i-1] + b[i-1]; // 2

  b[i] = a[i-1]; //1


a = {1, 2, 0}
b = {1, 1, 0}

  //i = 2
  
  a[i] = a[i-1] + b[i-1];
  
  b[i] = a[i-1];  

a = {1, 2, 3}
b = {1, 1, 2}

}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s