2.2 Kth smallest number 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.

e.g.

• 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

Assumptions: k >= 1

Input: int k

Output: long the kth smallest number

Solution:

1. Use pq and hashset (dedup)

2. Initial state: <x=1, y=1, z=1>

3. Expand <x, y, z>, generate

<x+1, y, z>

<x, y+1, z>

<x, y, z+1>

TC: k iterations, for each, 3log2k = O(klogk)

public long kth(int k) {
  PriorityQueue<Long> minHeap = new PriorityQueue<>(k);
  Set<Long> visited = new HashSet<>();
  minHeap.offer(3 * 5 * 7L); // Long expression
  visited.add(3 * 5* 7L);

  while (k > 1) {
    long cur = minHeap.poll();
    if (visited.add(3 * cur)) {
     minHeap.offer(3 * cur);
    }
    if (visited.add(5 * cur)) {
      minHeap.offer(5 * cur);
    }
    if (visited.add(7 * cur)) {
      minHeap.offer(7 * cur);
    }
    k--;
  }
  return minHeap.peek();
}