PROBLEM LINKAuthor : Ankit Sagwekar DIFFICULTYEasy
PREREQUISITESbasics,array,implementation PROBLEMGiven two integers 'm' and 'n'. Find the number of combinations of bitsize 'n' in which there are no 'm' consecutive '1'. EXPLANATIONWe are given with m and n. There are 3 cases for any given value of n and m
Note: for faster computation we can precompute all the values and can store them in 2D matrix. Complexity:(O(N^2.logN)) C++ Code
asked 23 Apr '15, 07:21

@skybolt :You will find many such recurrence relations in binary manipulations ,only thing you can do is play with them to find some newone's. Still we can prove the recurrence as follows: Consider m=2 Let’s call the function that calculate the number of ndigit binary numbers without two adjacent 1 bits a(n). Now let’s define two helper functions. a0(n) returns number of those binary numbers that end with zero, and a1(n) returns number of those ending with one. Thus, it’s obvious that: a(n) = a0(n) + a1(n) Now, suppose we already have a set of (n1)bit numbers generated and now, based on that, we want to generate a new set of nbit numbers. We’ll do that by adding a single bit to the end of each (n1)bit number. Because we care only about adjacent 1s, we can add 0s to the end of every (n1)bit number. Thus: a0(n) = a(n1) On the other hand we can’t add 1s to each (n1)bit number. We can only add 1 to numbers which had 0 at the end. Thus: a1(n) = a0(n1) By simple substitution we can rewrite the last equation into the following one: a1(n) = a(n2) Get back to the definition of a0(n) and a1(n) and make the final substitution: a(n) = a(n1) + a(n2) thus we can generalize the above method for m>2 Hope this solves your doubt :) answered 26 Jun '15, 22:35
