Problem Explanation

In this problem, we are given an integer as input and we need to determine if it's a "happy number". A happy number is a number that follows a certain process: Given a positive integer, we replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1, at which it will stay, or it will loop endlessly in a cycle which does not include 1.

For instance, if we take the number 19.

We first find the squares of the digits of 19 which is 1 and 9. The sum of the square of the digits is 1^2 + 9^2 = 82.

We then repeat the process. The sum of the squares of 8 and 2 (from 82) is 64 + 4 = 68.

This process is repeated until we reach 1 or the sequence loops endlessly. For 68, we get the sum of the squares as 100 and finally 1. Ascii illustration of the same:

1
2
319
4|
5v
682
7|
8v
968
10|
11v
12100
13|
14v
151

Since we reach 1, 19 is a happy number.

Solution Approach

The solution makes use of the Floyd's Cycle detection algorithm (also known as the Tortoise and the Hare algorithm). The algorithm is a pointer algorithm that uses two pointers which move through the sequence at different speeds.

In the context of our problem, the "slow" pointer, or tortoise, represents the sum of squares of the digits of the given number. The "fast" pointer, or hare, represents the sum of squares of the digits of the sum of squares of the digits.

The algorithm keeps moving the pointers till the slow and fast pointers meet which indicates the presence of a cycle. If the cycle is found and slow pointer points to 1, the number is a happy number. Otherwise, it's not.

Solutions

Python

1
2python
3class Solution:
4    def isHappy(self, n: int) -> bool:
5        def get_next(n):
6            return sum(int(x) ** 2 for x in str(n))
7        
8        slow = n
9        fast = get_next(n)
10        while slow != fast:
11            slow = get_next(slow)
12            fast = get_next(get_next(fast))
13        
14        return slow == 1

Java

1
2java
3class Solution {
4    public boolean isHappy(int n) {
5        int slow = n, fast = n;
6        do {
7            slow = calculate(slow);
8            fast = calculate(calculate(fast));
9        } while (slow != fast);
10
11        return slow == 1;
12    }
13
14    private int calculate(int n) {
15        int sum = 0;
16        while (n > 0) {
17            int digit = n % 10;
18            sum += digit * digit;
19            n /= 10;
20        }
21        return sum;
22    }
23}

JavaScript

1
2javascript
3var isHappy = function(n) {
4    let slow = n, fast = n;
5    do {
6        slow = calcSquareSum(slow);
7        fast = calcSquareSum(calcSquareSum(fast));
8    } while (slow !== fast)
9    
10    return slow === 1;
11};
12
13var calcSquareSum = function(n) {
14    let sum = 0;
15    while (n > 0) {
16        let digit = n % 10;
17        sum += digit * digit;
18        n = Math.floor(n / 10);
19    }
20    return sum;
21};

C++

1
2cpp
3class Solution {
4public:
5    bool isHappy(int n) {
6        int slow = n, fast = n;
7        do {
8            slow = compute(slow);
9            fast = compute(compute(fast));
10        } while (slow != fast);
11        return slow == 1;
12    }
13
14private:
15    int compute(int n) {
16        int sum = 0;
17        while (n) {
18            int digit = n % 10;
19            sum += digit * digit;
20            n /= 10;
21        }
22        return sum;
23    }
24};

C#

1
2csharp
3public class Solution {
4    private int GetNext(int n) {
5        int sum = 0;
6        while (n > 0) {
7            int d = n % 10;
8            n = n / 10;
9            sum += d*d;
10        }
11        return sum;
12    }
13    
14    public bool IsHappy(int n) {
15        int slow = n, fast = n;
16        do {
17            slow = GetNext(slow);
18            fast = GetNext(GetNext(fast));
19        } while (slow != fast);
20        return slow == 1;
21    }
22}

Discussion

These solutions, while written in different programming languages, follow the same basic approach. They all use a variant of the Floyd Cycle detection algorithm, looping until the fast and slow pointers meet. If they meet at 1, the original number is a happy number.

The interesting part to note is the different language syntaxes for handling digits. For example, JavaScript uses a while loop to calculate the sum of squares of digits, utilizing modulus and Math.floor() to handle division and remainders.

Python, in contrast, converts the number to a string, allowing it to iterate over each digit in the number. Each digit is converted back to an integer, squared, and the results are summed.

Java, like JavaScript, calculates the sum of squares of digits using a while loop with modulus and floor division.

Despite the language differences, the fundamental logic of the solutions remain the same, which emphasizes the cross-language versatility of the Floyd's Cycle detection algorithm. This algorithm can be a powerful tool when dealing with sequences or lists where detection of a cycle or repeating pattern is needed—whether that be to detect a happy number, identify a cycle in a linked list, or to solve some other pertinent problem.