 # 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  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.

Here is the code : https://ideone.com/rTdKUg

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

Do anyone receive interview call letter from NCR?