Find The K-th Lucky Number

Updated on 30 May, 2025
Find The K-th Lucky Number header image

Problem Statement

Lucky numbers are a special set of numbers in mathematics defined by the presence of specific digits. In this problem's context, only the digits 4 and 7 are considered lucky. Consequently, a number is termed as lucky if it consists exclusively of these digits – either 4 or 7 or both. The task here is to determine the kth lucky number where the definition of lucky has been specifically restricted to numbers containing only the digits 4 and 7. Given an integer k, your challenge is to find and return this kth lucky number, with the output represented as a string.

Examples

Example 1

Input:

k = 4

Output:

"47"

Explanation:

The first lucky number is 4, the second one is 7, the third one is 44 and the fourth one is 47.

Example 2

Input:

k = 10

Output:

"477"

Explanation:

Here are lucky numbers sorted in increasing order:
4, 7, 44, 47, 74, 77, 444, 447, 474, 477. So the 10th lucky number is 477.

Example 3

Input:

k = 1000

Output:

"777747447"

Explanation:

It can be shown that the 1000th lucky number is 777747447.

Constraints

  • 1 <= k <= 109

Approach and Intuition

Understanding the sequence and generation of lucky numbers is imperative to tackling this problem. Here's how we can think about approaching this:

  1. Lucky Number Generation:

    • Lucky numbers are essentially binary-like with only two digits, 4 and 7. Starting from the smallest (smallest in terms of value), the sequence begins with 4, then 7.
    • After single digits, we expand by considering all possible combinations of 4 and 7 with two digits: 44, 47, 74, 77, and so forth.
    • The lengthier the string, the permutations rise exponentially as every additional digit spot can be filled with either 4 or 7.
  2. Ordered Sequence Extraction:

    • As we are interested in the kth lucky number, knowing the position in an ascending sequence is essential. As such, generating the lucky numbers in order might not be computationally feasible, especially for large k, due to the exponential increase in possibilities.
  3. Kth Element Extraction Technique:

    • Instead of generation and counting, leveraging a mathematical or algorithmic way of directly pinpointing the kth sequence element based on its properties (similar to binary conversion but limited to 4 and 7) might be computationally efficient.
    • This can include breaking down k in a manner that reflects which 'binary' position (4 or 7) applies at various place values, treating 4 as 0 (binary) and 7 as 1.

By understanding and structuring the process of lucky number generation and sequence determination, we can navigate towards finding the kth element effectively, considering the constraints provided. The aforementioned examples also illustrate how this ordering and accumulation of lucky-number sequences unfold, allowing us to grasp the run-through of gradually complex sequences as k increases.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    string getLuckyNumber(int n) {
        n += 1;
        int numDigits = log2(n);
        string luckyNum(numDigits, ' ');
        while (n > 1) {
            numDigits--;
            luckyNum[numDigits] = (n % 2) ? '7' : '4';
            n /= 2;
        }
        return luckyNum;
    }
};

This solution in C++ focuses on finding the k-th lucky number, where a lucky number is composed of digits 4 and 7 only. Here's the breakdown of how this solution works:

  1. Increment the input n by 1 to adjust for zero-based indexing, as counting starts from 1 but array indexing in programming languages typically starts from 0.
  2. Calculate the number of digits required to represent n in binary form using log2(n). This value determines the number of characters in the resulting string luckyNum.
  3. Initialize luckyNum with the calculated number of spaces. This string will store the resulting lucky number.
  4. Use a while loop to convert n into a binary-like form where instead of binary digits (0 and 1), you use '4' and '7'. This conversion works as follows:
    • Continuously decrement numDigits to fill characters in reverse (from least significant digit to the most).
    • Determine the character to place ('7' for odd numbers and '4' for even numbers) by checking if n % 2 results in 1 (odd) or not (even).
    • Update n by dividing it by 2 iteratively to move to the next binary digit.
  5. Return luckyNum once all positions are filled, representing the k-th lucky number where the computation is a creative use of binary representation with custom substitutions.
java
public class Solution {

    public String findLuckyNumber(int index) {
        // Adjust index for 1-based calculation
        index = index + 1;

        // Determine binary representation and remove leading '1'
        String binaryStr = Integer.toBinaryString(index).substring(1);

        char[] luckyNumber = binaryStr.toCharArray();

        // Transform binary '0' to '4' and '1' to '7'
        for (int pos = 0; pos < luckyNumber.length; pos++) {
            luckyNumber[pos] = (luckyNumber[pos] == '1') ? '7' : '4';
        }

        return new String(luckyNumber);
    }
}

The Java program defines a method findLuckyNumber designed to find the K-th lucky number by converting its index in a unique sequence. The lucky numbers specifically use the numerals 4 and 7, which are popular in certain cultures.

  • The program begins by adjusting the index to accommodate a 1-based system as Java inherently uses a 0-based index.
  • To generate the lucky number, the method computes the binary representation of the adjusted index and then modifies it by discarding the initial character.
  • The resulting binary string is manipulated by replacing each '0' with '4' and each '1' with '7'.
  • This replacement is done through a loop that iterates over the characters of the binary string, making the appropriate substitutions.

The method finally returns the constructed string, which represents the K-th lucky number derived from its binary form. Make sure to pass the appropriate index to retrieve the correct lucky number sequence.

python
class Solution:
    def findLuckyNumber(self, index: int) -> str:
        # Update index to consider 1-based index system
        index += 1

        # Convert index to binary, skip '0b1' prefix
        lucky_number = bin(index)[3:]

        # Transform '0' to '4' and '1' to '7'
        lucky_number = lucky_number.replace("0", "4").replace("1", "7")

        return lucky_number

The Python solution focuses on finding the K-th "lucky number," which transforms a 1-based index into a string representation of binary digits, then replaces those digits with specific numbers, '4' or '7'. Here's how you can understand the approach taken in the provided solution:

  • First, adjust the given K-th index to accommodate a 1-based indexing system by incrementing the index by 1.

  • Convert the revised index into its binary form. Python's binary conversion outputs a string that starts with '0b', indicating that the number is binary.

  • Remove the initial '0b1' from the string to reshape the binary representation properly.

  • Replace each binary '0' digit with '4' and each '1' digit with '7' to construct the K-th lucky number in its final string form.

This method ensures that you convert an integral index into a special transformation based on a binary representation, transitioning each bit into either '4' or '7' rather than the typical '0' or '1'.

Comments

No comments yet.