Implement "No consecutive 1s" in C++

[jainnipun]

This is a(n):

• [x] New algorithm
• [ ] Update to an existing algorithm
• [ ] Error
• [ ] Proposal to the Repository

Details:

Details: Solves #2288

Added in new folder code/dynamic_programming/no_consec_ones

[mudit8560]

I am interested in it.Please guide me what I have to do in this.

[ghost]

hello , I'm interested in implementing this algorithm. please guide me how to do it.

[AdiChat]

@mudit8560 @arcade0 You need to clone Cosmos, commit changes to your local working copy and create a pull request 👍

[jainnipun]

@mudit8560 @arcade0
This is a simple algo counting the number of all binary representations having non - consequtive 1s for given length. e.g. for for given length 3

All possible binary representations: 000 001 010 011 100 101 110 111

but of these 3 representations have consecutive 1s (011, 110 , 111) so for input=3 output =5.

Logic followed here is that we start building our vector from base for n=1 we can have strings 0 and 1 so output =2 now at each step proceeding if we count strings if we add 0 and strings if we add 1 we can add 0 to all previous as it will not result in consecutive 1s but we can add 1 to only those which do not end in 1.

For given length n we just need to add all strings ending at 0 and 1 at n-1.

This was the algo. Code can be seen in my commit.

Link: http://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/

[Priya-Raut]

@AdiChat I would like to solve this issue in Java. Please assign it to me.