A fun way to practice or learn a language is to solve puzzles that are available on the Internet. One of those problems is the Ugly Numbers problem. It is special in that it, like many other problems, has multiple solutions with varying levels of efficiency.
The Ugly Number problem is: find the nth ugly number.
An Ugly Number is defined as a number whose factors are only 2, 3, and/or 5 (1 is accepted as an Ugly Number). So straight out of the gate 2, 3, and 5 are ugly numbers. 4 is also an ugly number as its only factor is 2 (2*2). 6 is an ugly number because its factors are only 2 and 3 (2*3). 7 is not an ugly number as its only factor is 7, and this eventually rules out 14, 21, etc.
As this is the first of the series I will be quite verbose about how to create the project. Future series will just refer to this one.
Factorization
The first solution is to go through all the Integers and return the nth one that you find. This really boils down to the question: how do you check if a number is ugly or not? First one must understand factorization…
To the left is the factor tree of the number 60. Numbers always have the factors of 1 and itself so that is not interesting or relevant to number ugliness. The order that the numbers are picked for factorization does not matter. In this case 6 and 10 were selected first. Those numbers are then factored until a prime number is reached. In the image 6 and 10 were selected as the first numbers to factor. While there is no problem with this, it is not a selection that a computer can make by simply viewing the value.
It is possible to reach the same solution by dividing by incrementing primes [2, 3, 5, 7…]. For instance 60 / 2 = 30. This produces the factors 2 and 30. 30 is even and thus can be divided by 2 again (30 / 2 = 15). This produces another 2 factor and 15. 15 cannot be divided by 2 anymore (as it is odd) so we can divide by three. 15 / 3 = 5. This adds the factors 3 and 5. All the numbers, 2, 2, 3, 5 are prime and are the same as the solution produced by the tree. This method of factorization will be the way we determine if a number is ugly or not!
One way that I look at factorization is the notion of, “taking out the twos, then the threes, and so on.” This is a somewhat more direct description of the algorithm and can be easier to visualize.
Project Initialization
Create some directory somewhere where you can do this work. I prefer ~/dev/go/<project>.
mkdir -p ~/dev/go/uglynumbers cd ~/dev/go/uglynumbers
In order to get dependency support this needs to be a go module. Depending on your go version this is quite simple. The command requires a ‘module name’ and the best way to make a unique one is to just use your github url (you do have github, don’t you)? This repository does not need to exist or be created in github as it is just a way to make a unique module name.
go mod init github.com/roaet/uglynumbers
Is Ugly?
With the factorization algorithm under our belt we can change it up slightly to figure out if a number is ugly or not.
The IsUgly algorithm is as follows:
Given a number, n, return true if it is ugly and false if not 1. While the number is even, divide by 2 2. While the number is divisible by 3, divide by 3 3. While the number is divisible by 5, divide by 5 4. If the number isn't 1 at this point it is not ugly Example 1, n = 24 1a. 24 is even, divide by 2, n = 12 1b. 12 is even, divide by 2, n = 6 1c. 6 is even, divide by 2, n = 3, n is no longer even 2. 3 is divisible by 3, divide by 3, n = 1, return true Note: when n = 1 one can break out of the loop Example 2, n = 14 1a. 14 is even, divide by 2, n = 7, n is no longer even 2-3. Can't do these 4. n isn't 1, return false
IsUgly Implementation and Test
While there are many options for how this part goes I have elected to do the test-driven development (TDD) approach. We’re going to write our test prior to coding the meat of our IsUgly function.
First create a file called uglynumbers.go and put the following in it:
// uglynumbers.go
package main
func IsUgly(n int) bool {
return false
}
This is a stubbed version of our function so that the test can run without it being fully implemented. It does not need to be in package main but there is no harm in it being so at the moment.
Next make a new file called uglynumbers_test.go and put the following in it:
//uglynumbers_test.go
package main
import "testing"
func TestIsUgly(t *testing.T) {
var tests = []struct {
given int
expected bool
}{
{0, false},
{1, true},
{2, true},
{3, true},
{4, true},
{5, true},
{6, true},
{7, false},
{8, true},
{9, true},
{10, true},
{11, false},
{12, true},
{13, false},
{14, false},
{15, true},
}
for _, test := range tests {
res := IsUgly(test.given)
if res != test.expected {
t.Errorf("With %d = got %v, expected %v",
test.given, res, test.expected)
}
}
}
Because these two files are in the same package they have visibility of each other. IsUgly is available for the test to call without any import.
The use of the tests variable which is a slice of structs is known as table-driven testing. You create this slice and then iterate over it to do multiple tests within the same function. Unlike other languages the t.Errorf function will not end the test within this function on failure.
To run this test:
go test
The output of this should have quite a few failures:
$ go test
--- FAIL: TestIsUglyNumber (0.00s)
uglynumbers_test.go:30: With 1 = got false, expected true
uglynumbers_test.go:30: With 2 = got false, expected true
uglynumbers_test.go:30: With 3 = got false, expected true
uglynumbers_test.go:30: With 4 = got false, expected true
uglynumbers_test.go:30: With 5 = got false, expected true
uglynumbers_test.go:30: With 6 = got false, expected true
uglynumbers_test.go:30: With 8 = got false, expected true
uglynumbers_test.go:30: With 9 = got false, expected true
uglynumbers_test.go:30: With 10 = got false, expected true
uglynumbers_test.go:30: With 12 = got false, expected true
uglynumbers_test.go:30: With 15 = got false, expected true
FAIL github.com/roaet/algo_ugly 6.100s
The test begins by setting up a table of arguments and expected values that we want CheckIfUgly to produce. It loops through the elements of the slice (a struct) and provides given to CheckIfUgly. If the response (res) is not what is expected then the test will fail.
The values can either be calculated by hand or can be found on the Internet somewhere. In this implementation we defined 0 to be not-ugly.
Implementation of Ugly Check
func CheckIfUgly(n int) bool {
// A number is ugly if only prime factors are 2, 3, or 5.
if true || n == 0 {
return false
}
for n%2 == 0 {
n /= 2
}
for n%3 == 0 {
n /= 3
}
for n%5 == 0 {
n /= 5
}
return n == 1
}
The function IsUgly will take an integer and find out if it only has the expected factors. The way it does this is by removing the expected factors completely from the number. For example the n%2 == 0 checks if the number can be divided by two. If it can be it will then divide it by two and check again. Eventually it will become a number that cannot be divided by two (as even 2/2 = 1 and 1 cannot be divided by two evenly) and move to the next loop.
All the loops will remove the expected factors from the number given. If, after all the divisions have happened, the number is not 1 that means it has some other number it can be divided by. An example of this is the number seven (and all its multiples). Seven cannot be divided by any of the expected values and thus the number will still be seven at the end of the function.
The initial check is there to prevent an infinite loop when a user passes in zero (as 0%2 == 0 is always true).
Solution 1 – Iterative
Similar to how we developed the ugly check, for the Ugly Number solution we will create the test first. We will add this to our uglynumbers_test.go file.
func TestNthUglyNumber1(t *testing.T) {
var tests = []struct {
given int
expected int
}{
{0, 0},
{1, 1},
{2, 2},
{3, 3},
{4, 4},
{5, 5},
{6, 6},
{7, 8},
{8, 9},
{9, 10},
{10, 12},
{11, 15},
{100, 1536},
{150, 5832},
}
for _, test := range tests {
res := NthUglyNumber1(test.given)
if res != test.expected {
t.Errorf("With %d = got %v, expected %v",
test.given, res, test.expected)
}
}
}
This test is remarkably similar to the prior test we made! This is good for many reasons. First, we are essentially testing the same thing, number in and something (in this case an int) out. Second, it means our tests aren’t doing anything special at all. Finally, it makes it easier to understand overall what our tests, and thus the underlying code, is doing.
Finally we implement the solution in uglynumbers.go file.
func NthUglyNumber1(n int) int {
if n == 0 {
return 0
}
lastUgly := 1
for i := 1; i < n; i++ {
for j := lastUgly + 1; j < math.MaxUint32; j++ {
if IsUgly(j) {
lastUgly = j
break
}
}
}
return lastUgly
}
The interesting line-by-lines:
Line 7: generate numbers from our last ugly (to save some time) to forever to find the next ugly number
Line 8: is the number we generated ugly? if so store it and break, otherwise go on… go on..
Line 14: we have found N ugly numbers, this last one made must be what we are looking for
The solution shown here is brute force attempt that works up to a point where you want to see the thousandth or even hundredth ugly number.
Solution 2 – Dynamic Programming
The dynamic programming approach, a notion that will quickly be explained as an aside, requires a bit more analysis of the problem and a lot more math. The gains from the complexity of the solution are immediately apparent once one tries to find an ugly number of any high value. This solution scales for as much as your datatype can hold it.
Aside: Dynamic Programming
Straight from wikipedia:
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner
The act of breaking down a problem into simpler sub-problems is how it helps us here. Not all problems fit this method, so the trick is to find out if your problem does. Let’s find out if the ugly number problem can be benefited from this method (spoiler: it does).
Ugly Number Breakdown
Just to bring the problem back into the space: an ugly number is a number whose factors are only 2, 3, and 5. What is a factor? It is a number that is multiplied by something to create another number.
Let’s break down this problem into something simpler by defining a ‘super-ugly’ number that only has a factor of 2. People would say that this means they are even numbers, and they’d be right, but ignore them for now. What are some super-ugly numbers?
2 is one of them. As is 4, 6, 8, 10… This looks like a list of even numbers. How would one solve the problem of “give me the nth even number?” In our very small list the first even number is 2, the second is 4, and the fifth is 10. Do you see the pattern? The nth even number is N * 2! These are just multiples of 2.
Well that was pretty simple, so let’s make the super-ugly number now be one only with factors of 3. The list is 3 to start, then 6, 9, 12, 15… This looks like multiples of 3! That is exactly what they are and the same equation works here: the nth super-ugly number is N * 3.
If we were to define super-ugly for ones with only factors of 5 it would be the same thing: the nth super-ugly-only-five number is N * 5.
Does that mean we can combine the lists of these multiples to get a list of all ugly numbers? Let’s try it:
We know the first 11 ugly numbers (back to the original problem) are:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15
The the multiples 2, 3, and 5 are below:
Twos: 2, 4, 6, 8, 10, 12
Threes: 3, 6, 9, 12, 15, 18
Fives: 5, 10, 15, 20, 25, 30
If we take the numbers in ascending order what do we get?
2, 3, 4, 5, 6, 8, 9, 10, 12, 15
This is the same list of numbers as the ugly numbers we know (ignoring the 1 of course).
So our problem, the ugly number problem, can be split into three sub problems of multiples of 2, 3, and 5, and then recombining them in order! Now let’s try to implement the algorithm.
Dynamic Programming Solution (algorithm)
Let’s initially start with our three lists of multiples (smaller for this example) and combine them.
Twos: [2, 4, 6] ; Threes: [3, 6, 9] ; Fives: [5, 10, 15]
The smallest number of the three lists is the number that should go first. Or we are taking the minimum of the current leading element of each list:
minimum(2, 3, 5) = 2
Thus 2 is our first number, (ugly list is [2]), and since we already used it (ugly number list doesn’t repeat) we remove it from its list. Our lists are now:
Twos: [4, 6] ; Threes: [3, 6, 9] ; Fives: [5, 10, 15]
The next number is again the minimum of the three leading numbers:
minimum(3, 4, 5) = 3
Thus 3 is our next number, (ugly list is [2, 3]). If we repeat this a few times:
minimum(4, 5, 6) = 4 // ugly list now [2, 3, 4]
minimum(5, 6, 8) = 5 // ugly list now [2, 3, 4, 5]
Something happens when we hit 6. It is now leading in our twos multiple list and threes multiple list. They can’t repeat so we have to take them both off.
minimum(6, 6, 8) = 5 // ugly list now [2, 3, 4, 5, 6]
This works, but… Why is there always a but?
Creating all the multiple lists beforehand is a bit of the same problem of a lot of work and memory. If someone wanted the billionth ugly number you’d have to make three lists of up to very, very big numbers. There, “must be a better way!”
What we are getting from the lists are the ith multiple of each list. Could we just generate these multiples as we go? If a number is taken from the list, meaning it was the smallest, we just need to increment the multiplier for that list. If multiple numbers are the same we increment the number for all of them.
Dynamic Programming Solution II
We will start with the 1st multiple of each and set counters for each to 1:
two_m = 1 three_m = 1 five_m = 1
Then we find the minimum of the counters times their respective factor (2, 3, or 5):
minimum(2*two_m, 3*three_m, 5*five_m) = 2 or minimum(2*1, 3*1, 5*1) = 2
Because we used the twos here we need to increment the two’s counter two_m.
two_m = two_m + 1
Then we do it again:
minimum(2*two_m, 3*three_m, 5*five_m) = 3 or minimum(2*2, 3*1, 5*1) = 3
We used the threes here so we increment the three’s counter three_m the same way.
How do we know that we used the twos, or threes, or fives? The number we used is the same as the number returned from minimum at its current state. So the next step would be:
minimum(2*two_m, 3*three_m, 5*five_m) = 5 minimum(2*2, 3*2, 5*1) = 5 2 * two_m = 2 * 2 = 4 3 * three_m = 3 * 2 = 6 5 * five_m = 5 * 1 = 5
We used fives because it was the same as the value returned from minimum.
Which number used shows which counter to increment. If the current multiple is the same as the minimum value then increment the counter(s). This works except for one thing: what happens when a counter reaches seven?
Seven is an un-ugly number, a pretty number I guess? We would now need to check if the counter itself is an ugly number! Oh no this is not the kind of recursion we are looking for.
If only we had a list of numbers that could be safely multiplied to our numbers to make ugly numbers… We’re building it right now! An ugly number multiplied by another ugly number must produce an ugly number (that’s how factors work). What if we only use the counters to select which ugly number we are using?
Given the first 11 ugly numbers we have:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15
The way the twos would increase would be:
1 * 2 2 * 2 3 * 2 4 * 2 5 * 2 6 * 2 8 * 2
With a little analysis we can see this would work for the threes and the fives! Now our rule is:
If the current multiple is the same as the minimum value then increment the counter(s) that point to their current place in the ugly number list. Because the ugly number list will grow faster (or at the same rate) that our twos, threes, and fives will need multiplicands we can always know this list will have the index we need.
Let’s make this.
The Dynamic Programming Test
The test for it should look remarkably similar to the prior solution’s test. This is expected as they do the exact same thing! We will eventually combine the tests into one so the similarity is explicit. This test goes into uglynumbers_test.go file.
func TestNthUglyNumber2(t *testing.T) {
var tests = []struct {
given int
expected int
}{
{0, 0},
{1, 1},
{2, 2},
{3, 3},
{4, 4},
{5, 5},
{6, 6},
{7, 8},
{8, 9},
{9, 10},
{10, 12},
{11, 15},
{100, 1536},
{150, 5832},
}
for _, test := range tests {
res := NthUglyNumber2(test.given)
if res != test.expected {
t.Errorf("With %d = got %v, expected %v",
test.given, res, test.expected)
}
}
}
It would be great if we had a minimum function that took three arguments. Let’s make that for simplicity. Put this into your uglynumbers.go file.
func Min3(x, y, z int) int {
if x <= y && x <= z {
return x
}
if y <= z && y <= x {
return y
}
return z
}
A test should be made for this as well just to cover our bases but I will leave that for you.
Here is the solution (again uglynumbers.go file):
func NthUglyNumber2(n int) int {
if n == 0 {
return 0
}
var ugly = make([]int, n)
ugly[0] = 1
i2, i3, i5 := 0, 0, 0
m2, m3, m5 := 2, 3, 5
nextUgly := ugly[0]
for i := 1; i < n; i++ {
nextUgly = Min3(m2, m3, m5)
ugly[i] = nextUgly
if nextUgly == m2 {
i2++
m2 = ugly[i2] * 2
}
if nextUgly == m3 {
i3++
m3 = ugly[i3] * 3
}
if nextUgly == m5 {
i5++
m5 = ugly[i5] * 5
}
}
return nextUgly
}
The interesting line-by-lines:
Line 4: we need to store our list and it will need to store exactly n numbers
Line 7: start the index counters for each factor at zero, because ugly[0] has the 1 we need to multiply them by
Line 8: the minimums of each factor start at their 1 * factor value so we can start the selections
Line 13: store our ugly number in our list so it will be available before we start finding the next values
Line 14: if the ugly number selected is equal to our current twos minimum
Line 15: increment the counter of our twos place in the ugly list (this exists because we put it there beforehand on line 13)
Line 16: set our new twos minimum to the current place in the ugly list * 2
Finally, below are the two tests combined into one. It is a table of algorithms to use with the previous tests inside it! Test-ception!
func TestNthUglyNumber(t *testing.T) {
algos := []func(int) int{NthUglyNumber1, NthUglyNumber2}
for _, algo := range algos {
var tests = []struct {
given int
expected int
}{
{0, 0},
{1, 1},
{2, 2},
{3, 3},
{4, 4},
{5, 5},
{6, 6},
{7, 8},
{8, 9},
{9, 10},
{10, 12},
{11, 15},
{100, 1536},
{150, 5832},
}
for _, test := range tests {
res := algo(test.given)
if res != test.expected {
t.Errorf("With %d = got %v, expected %v",
test.given, res, test.expected)
}
}
}
}
Conclusion and Analysis
I have tried to calculate the clock time of both algorithms when looking for the one-billionth ugly number but the first algorithm hasn’t returned yet. It’s been about a week now… But the second algorithm returned nearly instantly.
Time Complexity
The first algorithm has time complexity of n (the outer loop) * m (the inner loop) * CheckIfUgly. CheckIfUgly is 3 loops of n-size, so C*n. We end up with a time complexity of O(n3). Whew! No wonder the first algorithm is still going!
The second algorithm has time complexity of n (the only loop), so O(n) — linear complexity.
Space Complexity
The first algorithm has constant space complexity as there is no storage of prior values anywhere.
The second algorithm has space complexity of O(n) because it uses an array to keep track of prior values.
Thoughts
This problem is a great example of how a little, or a lot, of analysis can truly make a solution shine. If you happen to be calculating ugly numbers on an embedded system with space for a few variables the first solution is what you will need to use, just don’t expect it to go fast with big numbers.
Thanks for reading!