Adjacent Bit Counts | Editorial by adist98

Let us define the dp state as :
dp[k][n][0] and dp[k][n][1]
The definition of above dp state is as follows :
"number of n bit string with adjBC() = k with last bit 0" and "number of n bit string with adjBC() = k with last bit 1".

Now, the only part left is to define the recurrence relation :

Case 1 :  When the last bit is assumed to be 0
If the last bit is assumed to be 0, then the number of bits in the string decrease by 1, i.e., from n to n-1. So for dp[k][n][0], we can write :
dp[k]][n][0] = dp[k][n-1][0] + dp[k][n-1][1]
When the last bit is 0, we include the solution when the number of bits are n-1 and the penultimate bit is either 0 or 1, because if the last bit is 0 then the adjBC() will not increase no matter what the penultimate bit is.
Case 2 : When the last bit is assumed to be 1
If the last bit is assumed to be 1, then the penultimate bit can not be 1, because then the adjBC() will increase by 1. So for when the last bit is 1, we include the solution when number of bits are n-1 (because last bit is fixed as 1) and the penultimate bit is 0 and the value of k remains same.

Also, if the ultimate bit is 1 then we can also add all the values when k is one less i.e., k-1 and the final bit of n-1 bit string is 1. That way if we add 1 to an n-1 bit string with adjBC() = k-1, we will get a string whose adjBC() is k. So we have to count all those ways too in the solution when the last bit assumed to be 1.

So for dp[k][n][1] we can write :
dp[k][n][1] = dp[k][n-1][0] + dp[k-1][n-1][1]

The total number of adjBC() would then be 
 => dp[n][k][0] + dp[n][k][1]

Adjacent Bit Counts | Editorial by adist98

Download submission

All caught up!

View submission

Is your resume even shortlisted?