Coding

Find the Kth Lucky Number

Asked at

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

We know that 4 and 7 are lucky digits. Also, a number is called lucky if it contains only lucky digits.

You are given an integer k, return the kth lucky number represented as a string.

Input : k = 3 Output : "44" Explanation : The first lucky number is 4, the second one is 7and the third lucky number is 44.

Input : k = 1000 Output : "777747447" Explanation : It can be shown that the 1000th lucky number is 777747447.

**Input : **k = 15

1 <= k <= 109

cpp

class Solution {
    public:
        string kthLuckyNumber(int k) {
            //your code goes here
        }
};

java

class Solution {
    public String kthLuckyNumber(int k) {
        //your code goes here
    }
}

python

class Solution:
    def kthLuckyNumber(self, k: int) -> str:
        #your code goes here

javascript

class Solution {
    kthLuckyNumber(k) {
        //your code goes here
    }
}

csharp

class Solution
{
    public string KthLuckyNumber(int k)
    {
        //your code goes here
    }
}

func kthLuckyNumber(k int) string {

}

Stuck? Show a way to structure it+

01Count how many strings each length contributes
02Locate the length containing k
03Convert the within-level index to exactly L bits
04Map bits to digits and return

Reference answer

Start by restating the input contract for Find the Kth Lucky Number and testing the smallest boundary case before choosing the algorithm. A lucky number is formed only from digits 4 and 7. Map k to a binary-tree level: the numbers of length L occupy k values after all shorter lengths. Subtract whole levels, then use the remaining zero-based index as bits, with 0 mapped to 4 and 1 mapped to 7. Explain the invariant while coding, then show how each update preserves it. The generated number has O(log k) digits, so locating and emitting it takes O(log k) time and O(log k) space for the output. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

What is the kth number using digits 0, 1, and 2?
Tests: follow-up reasoning
Can you derive the answer without enumerating strings?
Tests: follow-up reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question