> For the complete documentation index, see [llms.txt](https://zhongquan789.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongquan789.gitbook.io/leetcode/lcci/mian-shi-ti-17.09.md).

# 面试题 17.09

Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7. Note that 3, 5, and 7 do not have to be factors, but it should not have any other prime factors. For example, the first several multiples would be (in order) 1, 3, 5, 7, 9, 15, 21.

Example 1:

Input: k = 5

Output: 9

## Solutions

* The same as `problem 264 Ugly number II`.
* **treeset**

```cpp
class Solution {
public:
    int getKthMagicNumber(int k) {
        set<size_t> s {1};
        for (int i = 1; i < k; i++) {
            auto min = *s.begin();
            s.erase(s.begin());
            s.insert({min * 3, min * 5, min * 7});
        }
        return *s.begin();
    }
};
```

1. **dynamic programming or merge sorted lists**

```cpp
class Solution {
public:
    int getKthMagicNumber(int k) {
        vector<int> dp(k + 1, 1);
        int i3 = 0, i5 = 0, i7 = 0;
        for (int i = 1; i < k; i++) {
            int minval = min(dp[i3] * 3, min(dp[i5] * 5, dp[i7] * 7));
            if (minval == dp[i3] * 3)
                i3++;
            if (minval == dp[i5] * 5)
                i5++;
            if (minval == dp[i7] * 7)
                i7++;
            dp[i] = minval;
        }

        return dp[k - 1];
    }
};
```