Summary of the question:
You are given two numbers L and R 1 <= L <= R <= 10^18. We define a lucky number as a number which contains the pattern “101” in its bit representation. Given an integer K, we need to find the Kth lucky number between L and R (both inclusive) if it exists, otherwise return -1.
My Approach:
So I tried to check every no. between L and R if it had 101 in its bit representation. For some testcases it passed, but for others I got TLE.
Please can someone provide me the most optimal solution/approach to this and these types of questions?
Do you mean that the bit representation should be like 101010101 or it should contain 101 as a substring in the bit representation
Why can't this be one of the possibilities ? **101
This got covered in 101** but i missed 1101 and other such cases.
what is the solution to this ?
binary search with digit dp is my first thought (let f(x) be the number of lucky numbers less than or equal to x, which is solvable with digit dp. Then simply BS for the minimum x such that f(x) — f(l-1) = k).