Skip to content

Instantly share code, notes, and snippets.

@ylegall
Created November 27, 2013 02:14
Show Gist options
  • Save ylegall/7669660 to your computer and use it in GitHub Desktop.
Save ylegall/7669660 to your computer and use it in GitHub Desktop.
Generate hamming numbers in order
import java.util.*;
class Hamming
{
static List<Integer> getHamming(int n) {
int count = 1;
List<Integer> hams = new ArrayList<>();
Set<Integer> seen = new HashSet<>();
hams.add(1);
int next = 1;
Queue<Integer> q2 = new ArrayDeque<>();
Queue<Integer> q3 = new ArrayDeque<>();
Queue<Integer> q5 = new ArrayDeque<>();
while (count < n) {
q2.add(2 * next);
q3.add(3 * next);
q5.add(5 * next);
if (q2.peek() < q3.peek()) {
if (q2.peek() < q5.peek()) {
next = q2.poll();
} else {
next = q5.poll();
}
} else {
if (q3.peek() < q5.peek()) {
next = q3.poll();
} else {
next = q5.poll();
}
}
if (!seen.contains(next)) {
hams.add(next);
seen.add(next);
++count;
}
}
return hams;
}
public static void main(String[] args) {
List<Integer> hams = getHamming(21);
System.out.println(hams);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment