Finding the k-th Hamming Number
A positive integer is called a Hamming number (also known as a 3-smooth or ugly number) if its only prime factors are 2, 3, and 5. The sequence starts: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, ...
Given a positive integer $k$, return the $k$-th Hamming number in ascending order.
Constraints:
- $1 \leq k \leq 1{,}690$
- The $1{,}690$-th Hamming number fits in a 32-bit integer
Examples:
- Input: $k = 1$ -- Output: $1$ (by convention, 1 is the first Hamming number)
- Input: $k = 7$ -- Output: $8$ (the sequence is 1, 2, 3, 4, 5, 6, 8, so the 7th is 8)
- Input: $k = 12$ -- Output: $16$ (the sequence is 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16)
Hints
- Every Hamming number can be obtained by repeatedly multiplying smaller Hamming numbers by 2, 3, or 5 -- think about how to generate them in order without sorting.
- Maintain three pointers into the result array, one for each prime factor. The next Hamming number is always $\min(h[i_2] \times 2,\; h[i_3] \times 3,\; h[i_5] \times 5)$.
- After appending the new minimum, advance every pointer whose candidate equaled that minimum (not just one) -- this prevents duplicates like $6 = 2 \times 3 = 3 \times 2$ from appearing twice.
Worked Solution
How to Think About It: Every Hamming number has the form $2^a \cdot 3^b \cdot 5^c$ for non-negative integers $a, b, c$. The brute force approach -- check every integer up to some large bound and test whether it factors cleanly into 2s, 3s, and 5s -- is wasteful and requires knowing the bound in advance. The key observation: if $h$ is a Hamming number, then $2h$, $3h$, and $5h$ are also Hamming numbers. So you can generate the entire sequence by starting from 1 and repeatedly multiplying by 2, 3, and 5. The trick is doing this in sorted order without duplicates.
Algorithm: Maintain a result array $h$ and three pointers $i_2, i_3, i_5$ into it, each tracking "the last element I have already multiplied by this factor." At each step, the next Hamming number is the minimum of $h[i_2] \times 2$, $h[i_3] \times 3$, and $h[i_5] \times 5$. Append that minimum to $h$ and advance whichever pointer(s) produced it. Use if (not elif) for all three comparisons -- this handles ties. For example, $6 = 2 \times 3 = 3 \times 2$, so both $i_2$ and $i_3$ need to advance when 6 is chosen, otherwise 6 would appear twice.
Code:
```python def nth_hamming(k: int) -> int: h = [1] * k i2 = i3 = i5 = 0 next2, next3, next5 = 2, 3, 5
for i in range(1, k): h[i] = min(next2, next3, next5) if h[i] == next2: i2 += 1 next2 = h[i2] * 2 if h[i] == next3: i3 += 1 next3 = h[i3] * 3 if h[i] == next5: i5 += 1 next5 = h[i5] * 5
return h[k - 1] ```
Complexity: $O(k)$ time and $O(k)$ space. Each of the $k$ elements is computed with a constant-time min and a few comparisons. No sorting required.
Answer: The three-pointer DP generates Hamming numbers in sorted order in $O(k)$ time. The critical detail is using if (not elif) to advance all pointers that produced the minimum, which correctly deduplicates numbers like $6 = 2 \times 3$.
Intuition
This is a classic example of a merge-of-sorted-streams problem in disguise. Conceptually, you have three infinite sorted streams: $\{2, 4, 6, 8, \ldots\}$, $\{3, 6, 9, 12, \ldots\}$, and $\{5, 10, 15, 20, \ldots\}$ -- but each stream is itself defined recursively in terms of the Hamming sequence. The three-pointer approach efficiently merges these streams on the fly without materializing them, giving you the globally sorted sequence one element at a time.
The subtle bug that trips people up is using elif instead of if. With elif, when the minimum is a number that appears in two streams (like 6, which equals both $h[i_2] \times 2$ and $h[i_3] \times 3$), only one pointer advances and the number gets emitted twice. In quant work more broadly, this kind of off-by-one or deduplication error is exactly what breaks a distributed merge or a priority-queue-based event scheduler -- the logic looks right at first glance, and only fails on tie cases that are easy to miss in testing.