Welcome to Subscribe On Youtube

2802. Find The K-th Lucky Number

Description

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.

 

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

Solutions

Solution 1: Mathematics

According to the problem description, a lucky number only contains the digits $4$ and $7$, so the number of $n$-digit lucky numbers is $2^n$.

We initialize $n=1$, then loop to check whether $k$ is greater than $2^n$. If it is, we subtract $2^n$ from $k$ and increment $n$, until $k$ is less than or equal to $2^n$. At this point, we just need to find the $k$-th lucky number among the $n$-digit lucky numbers.

If $k$ is less than or equal to $2^{n-1}$, then the first digit of the $k$-th lucky number is $4$, otherwise the first digit is $7$. Then we subtract $2^{n-1}$ from $k$ and continue to determine the second digit, until all digits of the $n$-digit lucky number are determined.

The time complexity is $O(\log k)$, and the space complexity is $O(\log k)$.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public String kthLuckyNumber(int k) {
          int n = 1;
          while (k > 1 << n) {
              k -= 1 << n;
              ++n;
          }
          StringBuilder ans = new StringBuilder();
          while (n-- > 0) {
              if (k <= 1 << n) {
                  ans.append('4');
              } else {
                  ans.append('7');
                  k -= 1 << n;
              }
          }
          return ans.toString();
      }
  }
  

• class Solution {
  public:
      string kthLuckyNumber(int k) {
          int n = 1;
          while (k > 1 << n) {
              k -= 1 << n;
              ++n;
          }
          string ans;
          while (n--) {
              if (k <= 1 << n) {
                  ans.push_back('4');
              } else {
                  ans.push_back('7');
                  k -= 1 << n;
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def kthLuckyNumber(self, k: int) -> str:
          n = 1
          while k > 1 << n:
              k -= 1 << n
              n += 1
          ans = []
          while n:
              n -= 1
              if k <= 1 << n:
                  ans.append("4")
              else:
                  ans.append("7")
                  k -= 1 << n
          return "".join(ans)
  
  

• func kthLuckyNumber(k int) string {
  	n := 1
  	for k > 1<<n {
  		k -= 1 << n
  		n++
  	}
  	ans := []byte{}
  	for n > 0 {
  		n--
  		if k <= 1<<n {
  			ans = append(ans, '4')
  		} else {
  			ans = append(ans, '7')
  			k -= 1 << n
  		}
  	}
  	return string(ans)
  }
  

• function kthLuckyNumber(k: number): string {
      let n = 1;
      while (k > 1 << n) {
          k -= 1 << n;
          ++n;
      }
      const ans: string[] = [];
      while (n-- > 0) {
          if (k <= 1 << n) {
              ans.push('4');
          } else {
              ans.push('7');
              k -= 1 << n;
          }
      }
      return ans.join('');
  }
  
  

All Problems

All Solutions