Can someone tell me how to solve SUBNUMS question?

This can be solved by **DIGIT-DP**

**Let f(x)=count of numbers <=x with 101 substring in its binary representation.**

Then answer will be f®-f(l-1)

To find f(x),

First convert x to binary, then going left to right for each bit, place 0 or 1 in current position keeping current number<=x.

Construct **dp[pos][prev1][prev2][issmaller][isfound]**

**pos**=current position.

**prev1**=previous bit wrt pos

**prev2**=second previous bit wrt pos

**issmaller**=whether current number has become smaller than x or not(is still equal to x).

**isfound**=whether 101 has been found in current number or not

If you get prev1==0 and prev2==1 and you are placing current bit as 1, set isfound=1 (since substring 101 is found).

You can count the numbers having 101 as substring using isfound upon reaching the end of current number.

Your code is really hard to understand. Please try to rewrite the code with proper comments(if you can).

Thanks