Distinct binary strings of length n with no consecutive 1s

Count all possible distinct binary strings of length n with no consecutive 1s


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm Visualization




Code Snippet

			
package com.ideserve.virendra.questions;

public class Binary {
	
	public static int countBinary(int N)
	{
		if(N < 1)
			return 0;
		int C0 = 1;
		int C1 = 1;
		
		for(int i=1; i<N; i++)
		{
			int temp = C1;
			C1 = C0;
			C0 = C0 + temp;
		}
		
		return C0 + C1;
	}
	
	public static void main(String args[])
	{
			System.out.print(countBinary(4));
	}
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Virendra Karappa for compiling current post.

    Virendra Karappa

    Ninja Programmer