K'th Special Number in Range

A simple straightforward approach is to check the binary representation of each number in the range, as soon as we have found the K’th special number we can print it.

The steps are as follows :

1. Initialize a variable ‘cnt’ equal to 0, it will store the special numbers calculated so far.
2. Run a for loop to iterate through each element in the range [L, R].
3. For each element, check if (101)₂ exists in its binary representation, the easiest way to do this is by directly using bitshifts ( ‘<<’ and ‘>>’ ) as they directly allow us to check if i’th bit is ON or OFF, in case you don’t know about them then free to do use some other method. If you are able to find a (101)₂ subarray in the current number then increment the value of ‘cnt’ by one.
4. If the value of ‘cnt’ is equal to ‘K’ then return the value of the current element in the range.
5. If you have iterated through the entire range and were not able to find an answer then return -1.

This problem involves the knowledge of digit DP, refer to some resource/blog if this is your first encounter with this topic.

We will first build logic to calculate the number of special numbers in the range [0, X]. then we can calculate the number of special numbers in the range [0, L], let the count of these numbers be ‘cnt’, now we need to find the smallest number Y such that the range [0, Y] has at least ‘cnt’ + K special numbers. You are halfway done if you were able to figure out this, as this situation can easily be tackled by binary search. Why? Because the count of special numbers in the range [0, Y] is a monotonically increasing function and using binary search we can calculate the smallest value of Y for which the count is equal to ‘cnt’ + K.

We are now left with a method to find the number of special numbers in a range [0, Y] optimally. It may be possible for someone who is well versed with digit DP to figure out a way to tackle this, but with no prior knowledge, it is not likely you will be able to figure out the logic. To start with what digit DP actually is, we try to build a sequence (binary sequence here) from left to right. And see the possibility of placing the digit on the current position based on the fact that there was a matching prefix in the previous state or not, we do this to avoid the possibility to build a number that is greater than the right bound of our range. Therefore we need one state to keep the track of the digit currently we are working on and one state to check if there is a matching prefix or not, along with this we need additional states according to conditions in the question but for every digit DP question the two states discussed till now remain common. For this question, we need to store additional information whether we have already encountered a 101 subarray or not, we can use ‘ctr’ to store this, additionally, we need information about the last two digits, ie: if we are currently placing the i’th digit then we need information about the i+1’th and i+2’th digit, as if these are 1 and 0 respectively then placing 1 at the i’th position will generate a 101 subarray and thus we can set ‘ctr’ equal to one. We can implement this logic recursively, starting for the 31’st bit as all the input numbers are in the integer range, we can make recursive calls and end the recursion when we have reached the -1’th bit, (in short: we will try to fill all the bits from 31’st to 0’th).

The steps are as follows :

1. Initialize a matrix ‘dp’ of size equal to 32 * 4 * 2 * 2. 32 is used to traverse all the 32 bits as the given numbers lie in integer range.
   • 4 is used to store the information about the last 2 bits placed, that is: if the ‘i - 2’th bit was 1 and ‘i - 1’th bit was 0 then we will store the value 2 in this state as 2 = (10)₂.
   • 2 is used to keep the track of the matching prefix and the last state of 2 is used to keep the track of the previously encountered 101 subarray.
2. Make an initial call to calculate the special numbers in the range [0, L - 1] and store the answer calculated in ‘cnt’. Set the value of ‘cnt’ equal to cnt + K.
3. Apply binary search, set ‘low’ equal to ‘L’ and ‘high’ equal to ‘R’, for each iteration calculate ‘mid’ equal to (low + high) / 2.
   • Make the call to function to calculate the special numbers in the range from [0, mid], if the number of special numbers in greater than or equal to ‘cnt’ then we will store the value of ‘mid’ in ‘ans’ and search for a better answer to the left of ‘mid’ by setting ‘high’ equal ‘mid - 1’.
   • Else if the count of the special numbers in the range [0, mid] is less than ‘cnt’ then we will set ‘low’ equal to ‘mid + 1’.
4. In the recursive function to calculate the count of special numbers in the range [0, X], we will place the digits from left to right using the variable ‘i’ and the variable ‘prefix’ will help us determine the options we have to place at the ‘i’th’ position.
   • If the information about the previous two bits is stored in ‘last’ then if ‘last’ is equal to 2, and we are currently placing 1 at the ‘i’th’ bit then we will pass ‘ctr’ equal to 1 as we have successfully found the (101)₂ subarray.
   • Also to pass the information of the last two digits in the next recursive call we will simply have two options, either to pass (last % 2) + 0 if we are placing 0 at the i’th position or (last % 2) + 1  if we are placing 1 at the i’th position.
   • We end the recursion when ‘i’ is equal to -1, and return the value 1 or 0 depending on the value of ‘ctr’. Refer to the code for a better understanding.