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));
						data.add(number);
					}
				}
			}
		}
		Collections.sort(data);
		return data.get(k - 1);
	}

Solution:
Here is the algorithm:

  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.
	public static int getKthMagicNumber(int k) {
		if (k <= 0)
			return 0;
		int val = 1;
		Queue<Integer> Q3 = new LinkedList<Integer>();
		Queue<Integer> Q5 = new LinkedList<Integer>();
		Queue<Integer> Q7 = new LinkedList<Integer>();
		Q3.add(3);
		Q5.add(5);
		Q7.add(7);
		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();
					Q3.add(val * 3);
				}
				Q5.add(val * 5);
			}
			Q7.add(val * 7);
		}
		return val;
	}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: