Submission link ( http://codeforces.com/contest/914/submission/34580268 )

I used simple dfs but getting a WA.

I just want to know why this approach is wrong.

Problem Link (http://codeforces.com/contest/914/problem/C )

I think u didn’t read the question properly.

It’s saying that count those number such that it takes exactly k operation to reduce to 1.

Like:

11111

2

for this you can have 3 or 011 as 011->2 and 2 in binary is 10->1

similarly for 5 (101)->10->1

similarly for 15(1111)->100->1

In all these cases we perform operation k times(2 times)

I saw ur code.Try printing ur num value in binary ,u’ll get to Know.

And again u didnt get the point,we dount have to count numbers less than n which have k set bits.

Read my explaination again.

(Run your code for the test u were getting wrong and Print the num in binary form and see if u get any num = 1111 (you wont) )

actually in the code dfs() i am trying to do the same thing, to identify numbers having k set bits but not greater than n . Lets say if binary length of n is 8 then it will try to calculate all the numbers less or equal to n and having bit length less or equal to 8 (having k set bits). The variable CHAIN_LENGTH in dfs() will keep track of number of set bits doesn’t exceed k, if it does then the recurrence will simply return. As i am adding pow(2, k) each time this will make a single bit set to one at a time. please look at my submission once.