Leetcode 202 - Happy Number

In the last month I encountered multiple algorithmic tasks which involved the processing of individual digits in a number. And I found out a very common solution is to stringify the number and then process the letters as the separate digits. So I thought I’d share a better approach.

Leetcode Example

This is the assignment of Leetcode 202 problem, also called Happy Number.

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.
• 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.

Return true if n is a happy number, and false if not.

Examples

Example 1:

• Input: n = 19
• Output: true

• Explanation:
  12 + 92 = 82
  82 + 22 = 68
  62 + 82 = 100
  12 + 02 + 02 = 1

Example 2:

• Input: n = 2
• Output: false

Now I found this solution on Youtube: Google LOVES this coding interview question. It’s in Python and it goes something like this:

def isHappy(n: int) -> bool:
	seen = set()
	current = str(n)
	while current not in seen:
		seen.add(current)
		sum = 0
		
		for digit in current:
			digit = int(digit)
			sum += digit ** 2
		
		if sum == 1:
			return True
		current = str(sum)
	return False

The main grudge I have with this method is (as the post title suggests) that it

1. It first turns the number into a string
2. It then iterates over the letters of the string
3. Turns the letter back into a number
4. Does the calculation

You don’t have to deal with the string nonsense to solve this!!! This is a numerical task. The input is a number. You already have the number! Just work with it as it is!

Process a number digit by digit

You can get the last digit of a number by modulating it by 10.

42 % 10  # 2

We can “shift” the number and get rid of the last digit by dividing it by 10. Here we actually want to divide it so that we get an integer back, not a float.

42 // 10  # 4

This is basically all you need to solve this kind of problem. We could optimize further, but this is the heart of the task and it needed some love.

A better solution

This is a solution implementing the numerical approach explained above.

def isHappyNum(n: int) -> bool:  
    seen = set()  
	
    while n not in seen:  
        seen.add(n)  
        sum = 0  
		  
        while n > 0:  
            digit = n % 10  
            sum += digit * digit  
            n //= 10  
		  
        if sum == 1:  
            return True
        n = sum  # Try again for the summed number
    return False

It’s very similar to the previous one! Some key differences are

• I’m treating n as the current working value.
• Instead of looping over letters, the inner loop stops when n reaches zero

The rest is pretty much the same.

Benchmark

This is what we’re after. I’ve benchmarked the two implementations with the same inputs for 500k iterations.

Benchmarking 10 inputs with 500000 iterations:

isHappyNum:	 1.930453375
isHappyStr:	 31.234492208999995

The results are not surprising. The numerical approach runs circles around the string solution, being approximately 16x faster.

Main takeaway: Computers love numbers. Who would have guessed.

You can get the benchmark code on GitHub!

Programming language matters

I think language choice really matters when solving these kinds of Leetcode tasks. Python is fast to code in, but it also shields you from a lot of internal things that are important for efficient programming.

For example when accessing the digits, you get a str. In python, an element of a string is a string! This is sometimes convenient, but it also makes it super easy to fall into similar performance traps. In languages like Go, you would get a byte. This warns you that you are doing something wrong, because converting a byte into a string and the string then into an integer should set of alarm bells in your head.

I’d say pick a proper statically-typed compiled language if you are learning to program. Even if the goal of the task is just to implement an algorithm. Languages like Go, Java, C# or Swift are great to learn on. You can write a working code in Python or Javascript quickly, but it comes at a hidden cost. You will thank yourself in the long run!