Hamming Numbers in Java

The challenge

A Hamming number is a positive integer of the form 2ⁱ3^j5^k, for some non-negative integers i, j, 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 = 2¹35
• The third smallest Hamming number is 3 = 23¹5
• The fourth smallest Hamming number is 4 = 2²35
• The fifth smallest Hamming number is 5 = 235¹

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

The solution in Java code

Option 1:

public class Hamming {
  
  public static long hamming(int n) {
    long[] h = new long[n];
    h[0] = 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:

import java.util.Arrays;
import java.util.TreeSet;

public class Hamming {
    public static long hamming(int n) {
        if (n <= 0) return -1;
        TreeSet<Long> 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:

import java.util.PriorityQueue;

public class Hamming {

  public static long hamming(int n) {
    PriorityQueue<Long> minheap = new PriorityQueue<Long>();
    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

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));
  }

}