Given three prime number(p1, p2, p3) and an integer k. Find the first(smallest) k integers which have only p1, p2, p3 or a combination of them as their prime factors.
Example:
Input : Prime numbers : [2,3,5] k : 5
If primes are given as p1=2, p2=3 and p3=5 and k is given as 5, then the sequence of first 5 integers will be:
Note: The sequence should be sorted in ascending order
Solution:
Time: O(k) Space: O(k)
public class Solution { public int[] solve(int A, int B, int C, int D) { int[] result = new int[D]; int index = 0; PriorityQueue<Integer> minHeap = new PriorityQueue<>(); minHeap.offer(A); minHeap.offer(B); minHeap.offer(C); Set<Integer> visited = new HashSet<>(); while (index < D) { int next = minHeap.poll(); if (visited.add(next)) { result[index++] = next; minHeap.offer(next * A); minHeap.offer(next * B); minHeap.offer(next * C); } } return result; } }