> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/bfs/untitled.md).

# Kth Smallest With Only 3, 5, 7 As Factors

Find the Kth smallest number s such that s = 3 ^ x \* 5 ^ y \* 7 ^ z, x > 0 and y > 0 and z > 0, x, y, z are all integers.

**Assumptions**

* K >= 1

**Examples**

* the smallest is 3 \* 5 \* 7 = 105
* the 2nd smallest is 3 ^ 2 \* 5 \* 7 = 315
* the 3rd smallest is 3 \* 5 ^ 2 \* 7 = 525
* the 5th smallest is 3 ^ 3 \* 5 \* 7 = 945

**Solution:** MinHeap to track incremental increase

```java
public class Solution {
  public long kth(int k) {
    PriorityQueue<Long> minHeap = new PriorityQueue<>(k);
    Set<Long> visited = new HashSet<>();
    minHeap.offer(3 * 5 * 7L);
    visited.add(3 * 5 * 7L);
    while(k > 1){
      long current = minHeap.poll();
      if (visited.add(3 * current)){
        minHeap.offer(3 * current);
      }
      if (visited.add(5 * current)){
        minHeap.offer(5 * current);
      }
      if (visited.add(7 * current)){
        minHeap.offer(7 * current);
      }
      k--;
    }
    return minHeap.peek();
  }
}
```

TC: O(klog(N))

SC: O(K)