This question was asked in NCR codewars hackerearth challenge

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 :thinking::thinking:

Of course that will TLE…

For op it’s dp digit


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.

Here is the code :

1 Like

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
162 162
(which is the number you have given.)

Do anyone receive interview call letter from NCR?