How many numbers in range from L to R contains 101 as a substring in binary representation ? R<=1e18…Anybody knows how to solve this…Thanks in advance
1 Like
I am not quite sure if this is correct, but this article contains the same as in the question. I am just afraid if it will get a TLE 
Of course that will TLE…
For op it’s dp digit
2 Likes
Can you explain how you will solve using digit dp
Convert both L-1 and R in binary. Find number of numbers in 0 to L-1 with “101” and number of numbers in 0 to R having “101” then subtract the result. That will give the number of numbers between L to R having “101” . To find number of numbers in 0 to X having “101” just keep both 0 and 1 at each index in its binary form and also check whether number is not exceeding X , also keep a track of last three bits in each state . If last three bits in any state is “101” it means we have found a solution , make another variable as a state which signifies this and when we reach at last index check if we found any “101” and if we do return 1 else return 0.
Means we are only checking if last three bits are 101 or not.
what if a number having binary representation as 10100010 are you considering this one??
Go through my comment once again , I have provided the code also therefore you can check this case. As I told while generating the binary numbers I will keep track of last three digits in each state not last three digits of the number. Try checking for the testcase
1
162 162
(which is the number you have given.)
Do anyone receive interview call letter from NCR?