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

1. Initialize array magic and queues Q3, Q5 and Q7
2. Insert 1 into magic.
3. Insert 1*3, 1*5 and 1*7 into Q3, Q5 and Q7 respectively.
4. Let x be the minimum element in Q3, Q5 and Q7. Append x to magic.
5. 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.
6. Repeat steps 4 - 6 until we’ve found k elements.



1        public static int getKthMagicNumber(int k) {
2                 if (k <= 0) return 0;
3                 int val = 1;
4                 Queue<Integer> Q3 = new LinkedList<Integer>();
5                 Queue<Integer> Q5 = new LinkedList<Integer>();
6                 Queue<Integer> Q7 = new LinkedList<Integer>();
7                 Q3.add(3);
8                 Q5.add(5);
9                 Q7.add(7);
10                for (--k; k > 0; --k) { // We’ve done one iteration already.
11                        val = Math.min(Q3.peek().intValue(),
12                                  Math.min(Q5.peek().inValue(), Q7.peek().intValue()));
13                        if (val == Q7.peek()) {
14                                Q7.remove();
15                        } else {
16                                if (val == Q5.peek()) {
17                                        Q5.remove();
18                                } else { // must be from Q3
19                                        Q3.remove();
20                                        Q3.add(val * 3);
21                                }
22                                Q5.add(val * 5);
23                        }
24                        Q7.add(val * 7);
25                }
26                return val;
27       }