Handling Happy Numbers: Building a Set-like Data Structure

Today, as I was tackling some LeetCode problems (easy ones, of course :D), I stumbled upon an interesting one called Happy Number.

According to wikipedia, happy number is a set of number theory, a happy number is a number which eventually reaches 1 when the number is replaced by the sum of the square of each digit.

I.e. images below in wikipedia:

Creating set-like data structure

To check whether a value has already been processed (to avoid an infinite loop), I used a Set data structure. Since I’ve worked with Python before, I’m familiar with the built-in set type, which only allows unique values.

But in Go, there’s no built-in Set type, so I had to create one from scratch and implement some methods to mimic the same behavior.

type Set struct{
    elements map[string] struct{}
}

func NewSet() *Set{
    return &Set{
        elements: make(map[string]struct{}),
    }
}

func (s *Set) Add(value string){
    s.elements[value] = struct{}{}
}

func (s *Set) Contains(value string) bool {
    _, found := s.elements[value]
    return found
}

I define a Set struct with a map where:

• Key: string - the actual value i want to store
• Value: struct{} - an empty struct that uses zero bytes of memory

Why struct{}? Because i only care about the keys (whether a value exists), not the values. Just try to be as efficient as i can.
In addition, I also defined the NewSet method as a constructor and created two simple methods, Add & Contains, so that the Set I defined behaves like a typical Set.

Logic to solve happy number proble

func sumSquares(n int) int {
    // Convert numbers to strings so they can be accessed character by character
    numStr := strconv.Itoa(n)
    sum := 0

    for _, char := range numStr {
        // Convert characters back to numbers
        digit := int(char - '0')
        sum += digit * digit
    }

    return sum
}

func isHappy(n int) bool {
    seen := NewSet()

    for n != 1 {
        key := strconv.Itoa(n)
        if seen.Contains(key) {
            return false 
        }
        seen.Add(key)
        n = sumSquares(n)
    }
    return true
}

The sumSquares function calculates the sum of the squares of each digit of the number n by: converting n to a string, taking each character, converting it to a number, squaring it, and then adding them together.

The isHappy function is the main function in this program. First, it initializes a Set. Then, it loops as long as the value of n is not equal to 1. Inside the loop, the program checks whether the current number (converted to a string) already exists in the Set. If it does, this indicates a cycle has been detected, and the function returns false. If it doesn't exist yet, the number is added to the Set, and n is updated with the result from the sumSquares function. When n reaches 1, the loop terminates and the function returns true, meaning the number is a happy number.

Run the test

func TestIsHappy(t *testing.T) {
    tests := []struct {
        input    int
        expected bool
    }{
        {1, true},
        {19, true},
        {7, true},
        {2, false},
        {4, false},
        {100, true},
        {24323423, false},
    }

    for _, tt := range tests {
        result := isHappy(tt.input)
        if result != tt.expected {
            t.Errorf("isHappy(%d) = %v; want %v", tt.input, result, tt.expected)
        }
    }
}

I write some testcases (using table test), testing several numerical values that fall into the categories of happy numbers and non-happy numbers.

Benchmark test

func Benchmark(b *testing.B) {
    numbers := []int{1, 7, 19, 100, 12345, 999999}
    for i := 0; i < b.N; i++ {
        for _, num := range numbers {
            isHappy(num)
        }
    }
}

My isHappy() function takes an average of 1.547 nanoseconds to execute once on a single number (in a loop on numbers), and Go runs it hundreds of thousands of times to get an accurate average.
I know this isn't the best result possible, but there may be some improvement in the future.

Escape analysis

Let's talk about a subtle performance trade-off in our implementation. When i run Go's escape analysis tool, it tells us something interesting:

❯ go build -gcflags=-m happy_number/main.go
happy_number/main.go:13:9: &Set{...} escapes to heap

That innocent-looking & in our NewSet() function has consequences.

It feels natural—after all, i'im creating a new Set and want to use it throughout our function. But that pointer return type triggers something called "heap escape."

What's Actually Happening?

Every time i call NewSet():

1. Go allocates memory on the heap (slow), because of returning pointer
2. The garbage collector later has to clean it up

Before You Go...

Okay, confession time: I know this code could be better. 😅

The sumSquares function doing all those string conversions? Yeah, a bit overkill. And returning a pointer for a tiny Set struct? Probably not necessary.