Ugly numbers with a heap

Why this matters

Ugly numbers are a classic interview question, and the method behind them is useful beyond that question. The task is to produce items in sorted order without sorting a long list. Each new item comes from an item you already have, so the program never needs to check every integer.

A prime number has exactly two factors: 1 and itself. 2, 3, 5, 7 and 11 are primes. A prime factor is a prime that divides a number evenly. The prime factors of 12 are 2 and 3, because 12 equals 2 times 2 times 3. The prime factors of 14 are 2 and 7, because 14 equals 2 times 7.

An ugly number is a positive whole number whose prime factors are only 2, 3 and 5. The number 1 counts as ugly, because it has no prime factors at all. The sequence starts 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, and so on. The number 7 is not ugly, because 7 is a prime that is not 2, 3 or 5. The number 14 is not ugly, because it has the factor 7.

The task is to return the nth ugly number. For n equal to 10 the answer is 12. For n equal to 1690 the answer is 2123366400.

One way to find an answer is to test each integer in turn and count the ugly ones. That is far too slow. To reach the 1690th ugly number, the test would have to pass more than two billion integers. The method in this lesson builds the sequence instead. Each ugly number after 1 is 2, 3 or 5 times an earlier ugly number, so the program can generate the next one directly.

This lesson uses a min heap. A min heap is a tree stored in an array where the smallest item sits at the top, and std::priority_queue with std::greater gives one in C++. The lesson also shows a second method that needs no heap, which is useful to understand because it runs faster in practice. The heap basics are covered in the first two lessons of this module, so they are only recalled here where needed.

The idea: multiply up from what you have

Start with the list that holds only 1. The candidates for the next ugly number are the list's items multiplied by 2, 3 or 5. Take the smallest candidate that has not been used yet, add it to the list, and repeat.

Here are the first few steps, worked out by hand. Each row shows the state before the step.

list           candidates (x2, x3, x5)     smallest    result
1              2, 3, 5                     2           2nd
1, 2           4, 3, 5                     3           3rd
1, 2, 3        4, 6, 5                     4           4th
1, 2, 3, 4     6, 6, 5                     5           5th
1, 2, 3, 4, 5  6, 6, 10                    6           6th

Look at the fourth row. The number 6 appears twice among the candidates, once as 3 times 2 and once as 2 times 3. The method must add 6 to the list only once. The two approaches below handle this in different ways.

The method produces every ugly number and nothing else. Take any ugly number m greater than 1. It has at least one prime factor, and that factor is 2, 3 or 5. Divide m by that factor. The result is smaller than m and still has only 2, 3 and 5 as prime factors, so it is an earlier ugly number. That means m is one of the candidates made from an earlier ugly number, so the method reaches m. Nothing else is produced, because every candidate is an ugly number times 2, 3 or 5, and such a product has only those prime factors.

The method also always picks the right next number. Every ugly number not yet in the list is a candidate of some earlier ugly number, so it is already waiting. The smallest waiting candidate must therefore be the next ugly number in order.

Approach 1: a min heap of candidates

Keep a min heap of candidate numbers. Start the heap with 1. Each time the program pops the smallest candidate, it has found the next ugly number. It then pushes that number's multiples by 2, 3 and 5 onto the heap.

Duplicates are the problem. The number 6 can be pushed from 3 and from 2. To avoid two copies, keep a set of numbers already pushed. A std::unordered_set checks membership in roughly constant time. Before pushing a candidate, ask the set whether the candidate is new. Push it only if it is.

Here is the complete program. It defines the heap approach as a function, prints the first 12 results, and compares the answers for n equal to 10 and n equal to 1690.

#include <algorithm>
#include <cstddef>
#include <functional>
#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
 
long long nth_ugly_heap(int n) {
    std::priority_queue<long long, std::vector<long long>, std::greater<>> pq;
    std::unordered_set<long long> seen;
    pq.push(1);
    seen.insert(1);
    long long current = 1;
    for (int i = 0; i < n; ++i) {
        current = pq.top();
        pq.pop();
        for (long long factor : {2LL, 3LL, 5LL}) {
            long long next = current * factor;
            if (seen.insert(next).second) pq.push(next);
        }
    }
    return current;
}
 
long long nth_ugly_pointers(int n) {
    std::vector<long long> ugly;
    ugly.reserve(n);
    ugly.push_back(1);
    std::size_t i2 = 0;
    std::size_t i3 = 0;
    std::size_t i5 = 0;
    while (ugly.size() < static_cast<std::size_t>(n)) {
        long long next2 = ugly[i2] * 2;
        long long next3 = ugly[i3] * 3;
        long long next5 = ugly[i5] * 5;
        long long next = std::min({next2, next3, next5});
        ugly.push_back(next);
        if (next == next2) ++i2;
        if (next == next3) ++i3;
        if (next == next5) ++i5;
    }
    return ugly.back();
}
 
int main() {
    std::cout << "first 12 with heap:";
    for (int i = 1; i <= 12; ++i) std::cout << ' ' << nth_ugly_heap(i);
    std::cout << '\n';
 
    std::cout << "first 12 with pointers:";
    for (int i = 1; i <= 12; ++i) std::cout << ' ' << nth_ugly_pointers(i);
    std::cout << '\n';
 
    std::cout << "n=10 heap " << nth_ugly_heap(10) << " pointers " << nth_ugly_pointers(10) << '\n';
    std::cout << "n=1690 heap " << nth_ugly_heap(1690) << " pointers " << nth_ugly_pointers(1690) << '\n';
 
    bool all_agree = true;
    for (int n = 1; n <= 2000; ++n) {
        if (nth_ugly_heap(n) != nth_ugly_pointers(n)) all_agree = false;
    }
    std::cout << "heap and pointers agree for n = 1..2000: " << (all_agree ? "yes" : "no") << '\n';
    return 0;
}

The program is compiled with g++ -std=c++20 -Wall and run. The output is:

first 12 with heap: 1 2 3 4 5 6 8 9 10 12 15 16
first 12 with pointers: 1 2 3 4 5 6 8 9 10 12 15 16
n=10 heap 12 pointers 12
n=1690 heap 2123366400 pointers 2123366400
heap and pointers agree for n = 1..2000: yes

The function nth_ugly_heap has three parts. By default std::priority_queue returns the largest item, so the third template argument, std::greater<>, is what makes it a min heap. The heap starts with 1, and the loop runs n times. Each pass pops the smallest candidate, which is the next ugly number, and keeps it in current. The inner loop tries the three multiples. The line if (seen.insert(next).second) does two jobs at once. The insert call adds the number to the set and returns a pair, and .second is true only when the number was not already there. So a number is pushed only the first time it appears.

The loop runs n times, and each pass does up to three heap pushes and three set checks. The heap never holds more than about three times n items, so each push and pop takes O(log n) time. The whole function takes O(n log n) time and O(n) memory.

The long long type holds values up to about 9.2 times 10 to the power of 18. For n equal to 1690 the candidates reach about 10.6 billion, so long long is needed. The mistakes section shows what happens with int.

Approach 2: three pointers and no heap

The second method uses a useful property. The list of ugly numbers is sorted, and every new ugly number comes from an earlier one multiplied by 2, 3 or 5. Keep three pointers into the list. Pointer i2 marks the earliest number whose double has not yet been added to the list. Pointer i3 does the same for triples, and i5 for fives.

At each step, compute the three candidates: the number at i2 times 2, the number at i3 times 3, and the number at i5 times 5. The smallest of the three is the next ugly number. Add it to the list. Then move every pointer whose candidate equals the new number one step forward.

The last rule is the key to handling duplicates. The number 6 can come from i2 pointing at 3 or from i3 pointing at 2. When 6 is chosen, both pointers move forward. So 6 is added to the list only once, and no set is needed.

Example: tracing the first eight steps

The next program prints the three candidates and the chosen number for each of the first eight steps. It uses the same rules as the function above.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<long long> ugly{1};
    std::size_t i2 = 0;
    std::size_t i3 = 0;
    std::size_t i5 = 0;
    std::cout << "step  ugly[i2]*2  ugly[i3]*3  ugly[i5]*5  chosen\n";
    for (int step = 1; step <= 8; ++step) {
        long long next2 = ugly[i2] * 2;
        long long next3 = ugly[i3] * 3;
        long long next5 = ugly[i5] * 5;
        long long next = std::min({next2, next3, next5});
        std::cout << step << "     " << next2 << "            " << next3
                  << "            " << next5 << "            " << next << '\n';
        ugly.push_back(next);
        if (next == next2) ++i2;
        if (next == next3) ++i3;
        if (next == next5) ++i5;
    }
    return 0;
}

The output is:

step  ugly[i2]*2  ugly[i3]*3  ugly[i5]*5  chosen
1     2            3            5            2
2     4            3            5            3
3     4            6            5            4
4     6            6            5            5
5     6            6            10            6
6     8            9            10            8
7     10            9            10            9
8     10            12            10            10

Read the third row by hand. After two steps the list is 1, 2, 3. Pointer i2 moved past 1 when 2 was chosen, so it now points at 2, and its candidate is 2 times 2, which is 4. Pointer i3 moved past 1 when 3 was chosen, so it now points at 2, and its candidate is 2 times 3, which is 6. Pointer i5 still points at 1, so its candidate is 5. The smallest is 4, and it is chosen.

Row 4 shows the duplicate case. The candidates are 6 and 6 and 5. The smallest is 5, which is chosen, so only i5 moves. Row 5 then has 6 from i2 and 6 from i3. Both pointers move, and 6 is added once. Row 5 also shows the candidate from i5 as 10, because i5 now points at 2.

Row 6 shows a candidate of 8 from i2. Step 5 moved i2 past 3, so it now points at 4, and 4 times 2 is 8. The list is now 1, 2, 3, 4, 5, 6, and the next ugly number is 8.

Each step does a fixed amount of work: three multiplications, a minimum and a few comparisons. The method has no heap, so it takes O(n) time, which is less than the O(n log n) of approach 1. The memory use is also O(n), because the list must hold every ugly number up to the answer.

Checking the answers

Two methods that agree can still share a mistake in how they define the sequence. A separate check tests each number against the definition. The check asks, for every integer up to 1000, whether it is ugly. It divides out every factor of 2, 3 and 5. If the number left over is 1, the number is ugly.

The operator % gives the remainder after division, so x % p == 0 means that p divides x evenly. The line x /= p divides x by p. The loop while (x % p == 0) keeps dividing until p no longer divides x, which removes every copy of that factor.

Take 45 as a worked case. Dividing by 3 twice leaves 5. Dividing by 5 leaves 1, so 45 is ugly. Now take 14. Dividing by 2 leaves 7. Seven is not divisible by 2, 3 or 5, so the number left over is 7, not 1, and 14 is not ugly.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
 
bool is_ugly(long long x) {
    if (x <= 0) return false;
    for (long long p : {2LL, 3LL, 5LL}) {
        while (x % p == 0) x /= p;
    }
    return x == 1;
}
 
std::vector<long long> ugly_list(int n) {
    std::vector<long long> ugly{1};
    std::size_t i2 = 0, i3 = 0, i5 = 0;
    while (ugly.size() < static_cast<std::size_t>(n)) {
        long long a = ugly[i2] * 2, b = ugly[i3] * 3, c = ugly[i5] * 5;
        long long next = std::min({a, b, c});
        ugly.push_back(next);
        if (next == a) ++i2;
        if (next == b) ++i3;
        if (next == c) ++i5;
    }
    return ugly;
}
 
int main() {
    const long long limit = 1000;
    std::vector<long long> from_check;
    for (long long x = 1; x <= limit; ++x) {
        if (is_ugly(x)) from_check.push_back(x);
    }
    std::vector<long long> from_list;
    for (long long v : ugly_list(200)) {
        if (v <= limit) from_list.push_back(v);
    }
    std::cout << "ugly numbers up to " << limit << " found by checking each integer: " << from_check.size() << '\n';
    std::cout << "ugly numbers up to " << limit << " from the generated list: " << from_list.size() << '\n';
    std::cout << "the two lists are equal: " << (from_check == from_list ? "yes" : "no") << '\n';
    std::cout << "the 200th ugly number: " << ugly_list(200).back() << '\n';
    std::cout << "is_ugly(2123366400): " << (is_ugly(2123366400LL) ? "yes" : "no") << '\n';
    return 0;
}

The output is:

ugly numbers up to 1000 found by checking each integer: 86
ugly numbers up to 1000 from the generated list: 86
the two lists are equal: yes
the 200th ugly number: 16200
is_ugly(2123366400): yes

The check and the generated list agree on all 86 ugly numbers up to 1000. The check is a good test for small values, but it does not scale. To find the 1690th ugly number by checking each integer, the program would have to test about 2.1 billion integers. The generated list reaches the same answer after 1690 steps. When a fast method and a slow, obvious method agree on many inputs, the fast method is much more likely to be right.

The output also shows that ugly numbers become rarer as they grow. Only 86 of the first 1000 integers are ugly, and the 200th one is already 16200.

Common mistakes

Forgetting to skip duplicates in the heap

If the seen check is removed, the heap pushes 6 twice. The output below comes from a version of the heap function with the check removed. The program pops 9 numbers.

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
 
int main() {
    std::priority_queue<long long, std::vector<long long>, std::greater<>> pq;
    pq.push(1);
    std::cout << "without the seen set:";
    for (int i = 0; i < 9; ++i) {
        long long current = pq.top();
        pq.pop();
        std::cout << ' ' << current;
        pq.push(current * 2);
        pq.push(current * 3);
        pq.push(current * 5);
    }
    std::cout << '\n';
    return 0;
}

The output is:

without the seen set: 1 2 3 4 5 6 6 8 9

The second 6 is wrong. The sequence should have each ugly number once. The extra 6 takes the place that 8 should have, so every later number in the list is shifted by one.

Using int for the products

The values grow quickly. The 1690th ugly number, 2123366400, fits in an int, which holds values up to 2147483647. But that number times 5 is 10616832000, which does not fit. The program below reads a value and multiplies it by 5 as an int.

#include <iostream>
 
int main() {
    int current = 0;
    std::cin >> current;
    int next = current * 5;
    std::cout << next << '\n';
    return 0;
}

It is compiled with g++ -std=c++20 -Wall -fsanitize=undefined and given the input 2123366400. The sanitizer, a tool that checks for undefined behaviour at run time, reports:

ugly_overflow.cpp:6:9: runtime error: signed integer overflow: 2123366400 * 5 cannot be represented in type 'int'
2026897408

The number printed after the message is meaningless. Signed overflow is undefined behaviour in C++, so the program may print any value or behave in other strange ways. Use long long for every product, as both functions above do.

Advancing only one pointer

In the pointer method, a common error is to advance only the pointer that gave the smallest candidate. With that change, when 6 is chosen from i2, the pointer i3 still points at 2, and 6 comes up again as its candidate. The list then holds 6 twice. The rule is to advance every pointer whose candidate equals the chosen number. The code uses three separate if statements, not else if, for this reason.

Off-by-one in n

The value of n counts from 1. The first ugly number is 1. The function returns 1 for n equal to 1, and 2 for n equal to 2. A common mistake is to treat n equal to 1 as 2, which shifts every answer by one place. The test in the code above checks n equal to 10, which must return 12, and not 10.

Practice

Exercise 1. Which of these numbers are ugly: 14, 45, 49, 64? Give the reason for each.

Show the answer

45 and 64 are ugly. 45 equals 3 times 3 times 5, and 64 equals 2 to the power of 6. 14 is not, because it has the prime factor 7. 49 is not, because 49 equals 7 times 7.

Exercise 2. Using the list in the program output, what are the 13th and 14th ugly numbers?

Show the answer

The 13th is 18, and the 14th is 20. The 11th and 12th are 15 and 16, shown in the first 12 line of the output. Then come 18, which is 2 times 9, and 20, which is 4 times 5.

Exercise 3. Explain why approach 1 needs the seen set, but approach 2 does not.

Show the answer

In approach 1, the same product can be pushed from two different earlier numbers, such as 6 from 3 and from 2. The set blocks the second copy. In approach 2, every pointer whose candidate equals the chosen number moves forward at the same time, so the same number cannot be added twice.

Exercise 4. Explain why approach 1 takes O(n log n) time.

Show the answer

The loop runs n times. Each pass pops one item from the heap and pushes at most three. The heap never holds more than about three times n items, so each push or pop takes O(log n) time. Multiplying n passes by O(log n) per pass gives O(n log n).

Exercise 5. Change the pointer method so that it returns the smallest ugly number greater than a given value x. What stops the loop, and what is the answer for x equal to 100?

Show the answer

Replace the loop condition with while (ugly.back() <= x) and keep the body the same. The list grows in sorted order, so the loop stops at the first number greater than x, and that number is the last item in the list. Return ugly.back(). For x equal to 100 the answer is 108. The number 100 is ugly, and 108 (which is 4 times 27) is the next one.

Summary

• An ugly number has only 2, 3 and 5 as prime factors, and 1 is the first one.
• Every ugly number after 1 is 2, 3 or 5 times an earlier ugly number, so the sequence can be built directly.
• A min heap of candidates, with a set to skip duplicates, gives the answer in O(n log n) time.
• Three pointers into the sorted list give the same answer without a heap, and advancing every matching pointer removes duplicates.
• Use long long for the products, because the intermediate values pass the limit of int.