## Find the kth number with prime factors 3, 5 and 7

Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

My initial thoughts:
The $k$-th number can not be larger than $7^{k}$. Therefore we can enumerate all the satisfying numbers by iterating the exponent of 3, 5 and 7 from 0 to k. We then sort those numbers and retrieve the kth. Altogether it’s a $O(k^{3})$ algorithm.

My initial codes:

```	public static int findKthNumber(int k) {
int top = k;
List<Integer> data = new ArrayList<Integer>();
for (int i = 0; i <= top; ++i) {
for (int j = 0; j <= top; ++j) {
for (int l = 0; l <= (top + 2 - i - j); ++l) {
if (l >= 0) {
int number = (int) (Math.pow(3, i) * Math.pow(5, j) * Math
.pow(7, l));
}
}
}
}
Collections.sort(data);
return data.get(k - 1);
}

Solution:
Here is the algorithm:

Initialize array magic and queues Q3, Q5 and Q7
Insert 1 into magic.
Insert 1*3, 1*5 and 1*7 into Q3, Q5 and Q7 respectively.
Let x be the minimum element in Q3, Q5 and Q7. Append x to magic.
If x was found in:

Q3 -> append x*3, x*5 and x*7 to Q3, Q5 and Q7. Remove x from Q3.
Q5 -> append x*5 and x*7 to Q5 and Q7. Remove x from Q5.
Q7 -> only append x*7 to Q7. Remove x from Q7.
Note: we do not need to append x*3 and x*5 to all lists because they will already be found in another list.

Repeat steps 4 – 6 until we’ve found k elements.

public static int getKthMagicNumber(int k) {
if (k <= 0)
return 0;
int val = 1;
for (--k; k > 0; --k) { // We’ve done one iteration already.
val = Math.min(Q3.peek().intValue(),
Math.min(Q5.peek().intValue(), Q7.peek().intValue()));
if (val == Q7.peek()) {
Q7.remove();
} else {
if (val == Q5.peek()) {
Q5.remove();
} else { // must be from Q3
Q3.remove();
}
}
}
return val;
}

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});