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: 记得要去重

  public long kth(int k) {
    PriorityQueue<Long> pq = new PriorityQueue<>();
    Set<Long> hashset = new HashSet<>();
    pq.offer(3L * 5 * 7);
    hashset.add(3L * 5 * 7);
    for (int i = 1; i < k; i++) {
      long val = pq.poll();
      long a = val * 3;
      long b = val * 5;
      long c = val * 7;
      if (!hashset.contains(a)) {
        pq.offer(a);
        hashset.add(a);
      }
      if (!hashset.contains(b)) {
        pq.offer(b);
        hashset.add(b);
      }
      if (!hashset.contains(c)) {
        pq.offer(c);
        hashset.add(c);
      }
    }
    return pq.peek();
  }