Ugly numbers and comparators

Questions 1 to 5 of 8

1. 1. What does this program print? ``cpp #include <algorithm> #include <cstddef> #include <iostream> #include <vector> int main() { std::vector<long long> ugly{1}; std::size_t i2 = 0, i3 = 0, i5 = 0; while (ugly.size() < 7) { 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; } for (long long v : ugly) std::cout << v << ' '; std::cout << '\n'; } ``

   1 2 3 4 5 6 61 2 3 4 5 6 71 2 3 4 5 6 81 2 3 4 5 8 10
2. 2. What does this program print? ``cpp #include <iostream> #include <queue> #include <string> #include <vector> using namespace std; struct Job { string name; int priority; int seq; }; struct ByPriorityThenSeq { bool operator()(const Job& a, const Job& b) const { if (a.priority != b.priority) return a.priority < b.priority; return a.seq > b.seq; } }; int main() { priority_queue<Job, vector<Job>, ByPriorityThenSeq> pq; int next = 0; auto push = [&](string name, int p) { pq.push({std::move(name), p, next++}); }; push("A", 2); push("B", 1); push("C", 2); push("D", 3); push("E", 1); push("F", 2); while (!pq.empty()) { cout << pq.top().name << ' '; pq.pop(); } cout << '\n'; } ``

   D A F C B ED C A F E BA C F D B ED A C F B E
3. 3. A priority_queue<Item, vector<Item>, BadCompare> uses this comparator. What is the bug? ``cpp struct Item { int key; int id; }; struct BadCompare { bool operator()(const Item& a, const Item& b) const { return a.key <= b.key; } }; ``

   It reverses the keys, so the largest key comes out firstIt says two items with equal keys are less than each other, which breaks the rule that no item is less than itselfIt compares the ids too, so items with equal keys come out in a random orderIt needs a tie-break on id, because a heap cannot compare two items with the same key
4. 4. This program builds ugly numbers with three pointers, but its output has a repeated value: 1 2 3 4 5 6 6 8. Which line causes it? ``cpp #include <algorithm> #include <cstddef> #include <iostream> #include <vector> int main() { std::vector<long long> ugly{1}; std::size_t i2 = 0, i3 = 0, i5 = 0; while (ugly.size() < 8) { 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; else if (next == b) ++i3; if (next == c) ++i5; } for (long long v : ugly) std::cout << v << ' '; std::cout << '\n'; } ``

   The ugly.push_back(next); line, because it adds the value before the pointers moveThe else if before the i3 check, because when 6 comes from i2, i3 does not move and 6 is offered againThe std::min call, because it can return a value that is not one of the three candidatesThe while condition, because it stops one value too late
5. 5. Why can every ugly number after 1 be built from an earlier one?

   The ugly numbers are all the integers that have a factor of 2, 3 or 5Dividing an ugly number m greater than 1 by one of its prime factors gives a smaller ugly numberEvery ugly number is the sum of two earlier ones1 is the only prime factor that any ugly number has