WitchDoc's blog

Sprinklr Online Coding Test Question
By WitchDoc, history, 6 years ago, In English

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?

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Do you mean that the bit representation should be like 101010101 or it should contain 101 as a substring in the bit representation

→ Reply
»
6 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it 
101 represents 5
101* : represents numbers in range 10 - 11
101** : represents numbers in range 20 - 23
101*** : represents numbers in range 40 - 47
each * can be 0 or 1.
 and so on. 
Now lets calculate how many numbers less than L are lucky numbers. Its easy to think, without forgetting the case when L contains 101 as first three bits form MSB side, let this number be x. 
Then we calculate the (x + k)th Lucky number again using the pattern above, if this number is <= R, then output it otherwise answer is -1
Edit : I have missed something here, this approach is incorrect
→ Reply
»
9 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

what is the solution to this ?

→ Reply
  • »
    »
    9 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

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

    → Reply