LeetCode Challenge: Happy Number

This is the second question in the LeetCode 30 Day Challenge.

Problem

Write an algorithm to determine if a number n is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example:

Input: 19
Output: true
Explanation: 
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Before I explain various ways to solve this problem, I want to say that this problem is kind of stupid and interesting at the same time. You'll probably understand why once you solve it.

Initial Thoughts

After reading the problem statement you may have jumped into an editor and started writing code. Probably something like this

def sum_of_squares(n):
    s=0
    while n > 0:
        x = n%10
        s += x*x
        n //= 10
    return s

def solution(n):
    while True:
        n = sum_of_squares(n)

        if n == 1:
            return True
        else:
            # what do i do?

Now that you realize you might have missed something in the problem statement, you read it again and come across a very important hint:

or it loops endlessly in a cycle which does not include 1

It says that an unhappy number will loop endlessly in a cycle. This means that the sum of squares will eventually repeat.

So, all we need to do is check if we came across a repeated number other than 1. If so, we know that the original number is unhappy.

Approach 1:

In the last post, we came across 2 interesting data structures: Hash Maps and Hash Sets. Both of them help in storing unique data. Let's use a Hash Set since we don't need to store a key-value pair.

Algorithm:

1. Write a function to return the sum of squares of the digits of a number
2. Initialize an empty hashset called visited
3. Iterate infinitely
4. If num == 1 return True
5. Replace num with the sum of squares of its digits
6. If new num exists in visited return False otherwise add it to the set

Code:

def sum_of_squares(n):
    s=0
    while n > 0:
        x = n%10
        s += x*x
        n //= 10
    return s


def approach1(n):
    visited = set()
    while True:
        if n == 1:
            return True

        n = sum_of_squares(n)

        if n in visited:
            return False

        visited.add(n)

Complexity analysis:

Time complexity: O(log(n)) 
Space complexity: O(log(n))

Note

The previous algorithm has the best time complexity you can achieve so the following solutions will only improve space complexity. There are many other solutions that exploit various properties of Happy numbers but I want to use this as an opportunity to show an important concept and pattern used in Linked List problems.

Approach 2

As mentioned in the Note, this solution will be based on a common pattern used in Linked List problems. If you're not familiar then learn about them here.

The question is to find whether a linked list has a cycle in it or not.

This is how a linked list with a cycle looks like:

You can solve this problem using Hash Sets but the objective is to solve it with constant space complexity.

How? Two Pointers!

If two people run at different speeds in a circle, they eventually meet.

Now, you might wonder why will this always work? Here's the best proof I have come across. It uses simple modular arithmetic to explain it very intuitively.

If you're still not convinced then here's a natural example everybody comes across everyday but goes unnoticed.

The hands of a clock

The minute and hour hand of a clock move at different speeds, but they coincide 22 times a day. The above image shows 11 such times. These occur twice in a day every 12 hours resulting in 22 times. The times they coincide are weird which is why we don't notice them but they do.

They coincide because the space they move through is limited in the circle and since one hand is faster they are bound to meet.

The 2 pointers in a linked list are the same. They can move at any 2 speeds and they will meet if there is a cycle.

Can I use any 2 speeds for the pointers?

Yes, you can. However, we don't know how many minimum elements will be present in the cycle which is why 1:2 is the most common speed chosen.

So, you keep 2 pointers called slowptr and fastptr.
Initially, slowptr points to the head of the linked list and fastptr points to the 2nd element. Until slowptr and fastptr point to the same node you increment slowptr by 1 node and fastptr by 2 nodes.
If fastptr has crossed the end or is at the end while slowptr and fastptr are not the same then it means that there is no cycle.

All right, but how to use this?

In the Linked list problem slowptr and fastptr were variables that held nodes of the linked list, but since we're dealing with numbers we need to store numbers.

We increment nodes in a linked list so in our problem we get the next number with the sum_of_squares function. Now that we know how to use 2 pointers in our problem let's write the algorithm.

Algorithm:

1. Write a function to return the sum of squares of the digits of a number
2. Initialize slow = sum_of_squares(n)
3. Initialize fast = sum_of_squares(slow)
4. Iterate while slow != fast
5. Assign slow = sum_of_squares(slow)
6. Assign fast = sum_of_squares(fast) twice
7. If fast == 1 return True
8. When Step 4 ends, return slow == 1 because if n was 1 then step 4 wouldn't have begun.

Code:

def sum_of_squares(n):
    s=0
    while n > 0:
        x = n%10
        s += x*x
        n //= 10
    return s


def approach2(n):
    slow = fast = n

    slow = sum_of_squares(slow)
    fast = sum_of_squares(slow)

    while slow != fast:
        slow = sum_of_squares(slow)
        fast = sum_of_squares(fast)
        fast = sum_of_squares(fast)

        if fast == 1:
            return True

    return slow == 1

Complexity analysis:

Time complexity: O(log(n)) 
Space complexity: O(1)

Summary

Earlier in this post, I said that this problem was both stupid and interesting. It's stupid because at first glance it seems very easy and doesn't have any programmatic relevance. It's interesting because it can be used to learn something totally different but very useful.

I hope you understood the 2 pointer method because it can be used to solve many unrelated and weird problems efficiently in terms of both time and space.

Here's the repl for this problem.

Have fun coding ✨