Problem 202. Happy Number [Easy]

Description

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

A happy number is 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.

My First Solution [Time: O(log n), Space: O(k)]

def isHappy(self, n: int) -> bool:
        visited = set()
        while n != 1:
            if n in visited:
                return False
            visited.add(n)
            total = 0
            while n > 0:
                digit = n%10
                total += digit*digit
                n = n//10
            n = total
        return True

Floyd’s Tortoise and Hare Algorithm [Time: O(log n), Space: O(1)]

def isHappy(self, n: int) -> bool:    

        def get_next_number(n):    
            output = 0

            while n:
                digit = n % 10
                output += digit ** 2
                n = n // 10

            return output

        slow = get_next_number(n)
        fast = get_next_number(get_next_number(n))

        while slow != fast:
            if fast == 1: 
                return True
            slow = get_next_number(slow)
            fast = get_next_number(get_next_number(fast))

        return slow == 1

Notes

The first attempt is good but is not fully optimised for space complexity. The reason is due to using a set to track the seen numbers. This gives the function O(k) space complexity since the amount of memory required depends on the number of elements which need to be stored in the set visited before a cycle occurs, k.

Floyd’s cycle detection algorithm uses two pointers (fast and slow) to spot when a process has entered a cycle.
Slow: moves one node every iteration
Fast: moves two nodes every iteration
If fast is the same number as slow at any point, then you have a cycle.

Initially, I was unsure how it detects a cycle since the hare could “jump” the tortoise and thus they wouldn’t be equal and the algorithm wouldn’t recognise the cycle. I like this explanation: imagine fast and slow moving around a circle of nodes, since slow moves forward one step and fast moves forward two steps, fast is catching slow at a rate of one node every iteration. Thus, at some point fast will catch slow and the algorithm will return this as a cycle.

Couldn’t it detect a false cycle for some sequence of numbers? Say: 1, 1, 1, 3, 6, 7, 8, 5. It would immediately stop and say it’s a cycle because slow = 1 and fast = 1. However, this algorithm must be run on a sequence where each next number is given by a deterministic function. So by the property of a function that each input has a unique output, f(1) = 1 and f(1) = 3 can’t simultaneously be true.

C++ Version

int get_next(int n){
            int output = 0;
            while (n){
                int digit = n % 10;
                output += digit*digit;
                n = n/10;
            }
            return output;
    }

    bool isHappy(int n) {
        int slow = get_next(n);
        int fast = get_next(get_next(n));

        while (slow != fast){
            if (fast == 1){
                return true;
            }
            slow = get_next(slow);
            fast = get_next(get_next(fast));
        }
        return slow == 1;
    }