## The challenge

Hamming number is a positive integer of the form 2i3j5k, for some non-negative integers ij, and k.

Write a function that computes the _n_th smallest Hamming number.

Specifically:

• The first smallest Hamming number is 1 = 235
• The second smallest Hamming number is 2 = 2135
• The third smallest Hamming number is 3 = 2315
• The fourth smallest Hamming number is 4 = 2235
• The fifth smallest Hamming number is 5 = 2351

The 20 smallest Hamming numbers are given in example test fixture.

## The solution in Java code

Option 1:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````public class Hamming { public static long hamming(int n) { long[] h = new long[n]; h = 1; long x2 = 2, x3 = 3, x5 = 5; int i = 0, j = 0, k = 0; for (int index = 1; index < n; index++) { h[index] = Math.min(x2, Math.min(x3, x5)); if (h[index] == x2) x2 = 2 * h[++i]; if (h[index] == x3) x3 = 3 * h[++j]; if (h[index] == x5) x5 = 5 * h[++k]; } return h[n - 1]; } } ``````

Option 2:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 `````` ``````import java.util.Arrays; import java.util.TreeSet; public class Hamming { public static long hamming(int n) { if (n <= 0) return -1; TreeSet ts = new TreeSet<>(Arrays.asList(2L, 3L, 5L)); long smallest = 1; for (int i = 1; i < n; i++) { smallest = ts.pollFirst(); ts.add(smallest * 2); ts.add(smallest * 3); ts.add(smallest * 5); } return smallest; } } ``````

Option 3:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 `````` ``````import java.util.PriorityQueue; public class Hamming { public static long hamming(int n) { PriorityQueue minheap = new PriorityQueue(); minheap.add(2L); minheap.add(3L); minheap.add(5L); long curr = 1; for (int i = 1; i < n; i++) { curr = minheap.poll(); while (minheap.peek() == curr) {curr = minheap.poll();} minheap.add(curr*2); minheap.add(curr*3); minheap.add(curr*5); } return curr; } } ``````

## Test cases to validate our solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 `````` ``````import org.junit.*; import static org.junit.Assert.*; public class HammingTests { @Test public void Test1() { Assert.assertEquals("hamming(1) should be 1", 1, Hamming.hamming(1)); Assert.assertEquals("hamming(2) should be 2", 2, Hamming.hamming(2)); Assert.assertEquals("hamming(3) should be 3", 3, Hamming.hamming(3)); Assert.assertEquals("hamming(4) should be 4", 4, Hamming.hamming(4)); Assert.assertEquals("hamming(5) should be 5", 5, Hamming.hamming(5)); Assert.assertEquals("hamming(6) should be 6", 6, Hamming.hamming(6)); Assert.assertEquals("hamming(7) should be 8", 8, Hamming.hamming(7)); Assert.assertEquals("hamming(8) should be 9", 9, Hamming.hamming(8)); Assert.assertEquals("hamming(9) should be 10", 10, Hamming.hamming(9)); Assert.assertEquals("hamming(10) should be 12", 12, Hamming.hamming(10)); Assert.assertEquals("hamming(11) should be 15", 15, Hamming.hamming(11)); Assert.assertEquals("hamming(12) should be 16", 16, Hamming.hamming(12)); Assert.assertEquals("hamming(13) should be 18", 18, Hamming.hamming(13)); Assert.assertEquals("hamming(14) should be 20", 20, Hamming.hamming(14)); Assert.assertEquals("hamming(15) should be 24", 24, Hamming.hamming(15)); Assert.assertEquals("hamming(16) should be 25", 25, Hamming.hamming(16)); Assert.assertEquals("hamming(17) should be 27", 27, Hamming.hamming(17)); Assert.assertEquals("hamming(18) should be 30", 30, Hamming.hamming(18)); Assert.assertEquals("hamming(19) should be 32", 32, Hamming.hamming(19)); } } ``````