Solution: Find The K-th Lucky Number

Statement

A number is called lucky if it comprises only the digits $4$ and $7$. Your task is to return the k-th lucky number as a string for a given integer k. 

Constraints:

• $1 <=$ k $<= 10^9$

Solution

The essence of this solution lies in using bitwise manipulation to generate the k-th lucky number. The solution uses an approach by transforming the given integer k into a binary-like representation to determine the k-th lucky number. The key idea is to convert k into a string of digits composed of $4s$ and $7s$, the only digits considered lucky. This approach uses a combination of binary representation and simple string manipulation to construct the desired lucky number sequence.

Now, let’s walk through the steps of the solution:

1. We start by adjusting k for 1-based indexing. Since lucky numbers are usually counted starting from the first (i.e., 1-based indexing), we increment k by $1$. For example, if k $= 5$, it becomes $6$ after increment. This ensures the calculations align correctly with the expected sequence of lucky numbers.

2. Next, we build the binary representation of incremented k, excluding the most significant $1$ and any bits to the left of it. For example, if after increment k $= 6$, we convert it to $‘0b110’$ and to generate the lucky number, we exclude the most significant $1$ and the bits left to it. This leaves only the binary digits after the most significant $1$ that are $‘10’$.

3. Now, we replace binary digits with lucky digits in the resulting binary number. Every $‘0’$ is replaced with $‘4’$, and every $‘1’$ is replaced with $‘7’$. This replacement transforms the binary-like sequence into the required lucky number format. For instance, $‘10’$ becomes $‘74’$, aligning with the concept of lucky numbers composed of the digits $4$ and $7$.

4. Finally, the transformed string is returned as the k-th lucky number.

Let’s look at the following illustration to get a better understanding of the solution: