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(r)-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.
1 Like
Your code is really hard to understand. Please try to rewrite the code with proper comments(if you can).
Thanks