Day 4 of the Leetcode July Challenge presents an interesting number sequence problem. We are asked to find the $n-th$ “ugly” number, where ugly numbers are defined as positive numbers whose prime factors only include $2, 3, 5$, with the additional note that $1$ is also an ugly number.

$n = 10$

[1,2,3,4,5,6,8,9,10,12]

The 10th ugly number = 12.

My first thought on how to approach this problem is that we will need to either build the list of ugly numbers up to $n$ or iterate over those values. This meant that I would likely be trying a few different approaches for this problem. I started with what I felt would be the simplest to implement:

int nthUglyNumber(int n) {
   static const vector<int> uglyRoots = {2,3,5};
   set<long> uglyNumbers;
   uglyNumbers.insert(1);
   
   for(int i=1;i<n;i++) {
	  long current = *uglyNumbers.begin();
	  uglyNumbers.erase(current);
	  for(auto root : uglyRoots) {
		uglyNumbers.insert(current * root);
	  }
   }
   return *uglyNumbers.begin();
}

In my first algorithm, I use an ordered set to store to build the sequence, taking advantage of the set characteristics of unique elements and ordering, meaning it’s always possible to retrieve the least element from the set as the next ugly number. This is a decent, easy to remember approach with a time complexity of O(n log n)–log n for the set insertions as C++ ordered sets are implemented as balanced binary trees. I wasn’t quite happy with measured execution time though, and thought I would try to implement the same functionality by using the combination of a priority queue/min heap and an unordered set. I expected to see some benefits from the use of an unordered set’s constant time hashing, but the measured difference was minimal, as the min heap insertions maintained the algorithm’s overall runtime complexity of O(n log n).

int nthUglyNumber(int n) {
   static const vector<int> uglyRoots = {2,3,5};
   priority_queue<long, vector<long>, greater<long>> pq;
   unordered_set<long> seen;
   pq.push(1);
   for(int i=1;i<n;i++) {
	  long current = pq.top();
	  pq.pop();
	  for(auto root : uglyRoots) {
		 if(!seen.count(current * root)) {
			pq.push(current * root);
			seen.insert(current * root);
		 }
	  }
   }
   return pq.top();
}

While the two above algorithms are pretty good, I thought that I might be able to squeeze a little more performance out if I could find a way to avoid using those more complex data structures all together. To accomplish this, it’s necessary to build the list of ugly numbers one element at a time, while also ensuring that they are correctly ordered–the minimum next mulitple is always added next. This turned out to be simpler to implement than I anticipated. By maintaining index variables for each factor, we can essentially build three seperate factor lists on top of each other, only inserting the element from and iterating the list with the minimum element. This results in an improved asymptotic complexity of O(n).

int nthUglyNumber(int n) {
   vector<long> uglyNumbers = {1};
   int index2 = 0, index3 = 0, index5 = 0;

   while(uglyNumbers.size() < n){
	  uglyNumbers.push_back(min({uglyNumbers[index2]*2, uglyNumbers[index3]*3, uglyNumbers[index5]*5}));
	  if(uglyNumbers.back() == uglyNumbers[index2]*2) index2++;
	  if(uglyNumbers.back() == uglyNumbers[index3]*3) index3++;
	  if(uglyNumbers.back() == uglyNumbers[index5]*5) index5++;
   }
   return uglyNumbers[n-1];
}

Very cool stuff! I enjoy problems where I can take several different approaches and weigh the pros and cons of different data structures. Check back tomorrow for my take on another day of the July challenge.