Question

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)$.

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)

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;
  }
};

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('');
}