Leetcode Study Day 22

2023-10-15

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.

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
 

Constraints:

1 <= n <= 231 - 1

My solution

My solution is very intuitive, I convert the number to string and then convert each digit back to int and square it. Then I add all the squared digits together. I repeat this process until the sum is 1 or the iterate times achieve the maximum set. If the sum is 1, then the number is happy. If the loop is endless, then the number is not happy.

I learnt that in C++, we can use to_string() to convert a number to string and stoi() to convert a string to int.

If we want to convert a char to int, we can use char - '0'. The reason is that the ASCII value of ‘0’ is 48, ‘1’ is 49, etc. So if we want to convert ‘0’ to 0, we can use 48 - 48 = 0, for other digits, we can use 49 - 48 = 1, 50 - 48 = 2, etc.

Floyd Cycle Detection Algorithm

Firstly, let’s find out what is Floyd Cycle Detection Algorithm. It is also called Tortoise and Hare Algorithm.

Basic Idea:

The algorithm uses two pointers that move through the sequence at different speeds:

Tortoise (or slow pointer): Advances one step at a time.
Hare (or fast pointer): Advances two steps at a time.

If there’s a loop in the sequence, the hare will eventually catch up to the tortoise.

Relationship with the Happy Number Problem:

In the context of the happy number problem, the sequence is formed by repeatedly applying the “sum of the squares of its digits” operation. If a number is not happy, it will eventually fall into a cycle (or loop).

For example, for the number 4:

(4^2 = 16)
(1^2 + 6^2 = 37)
(3^2 + 7^2 = 58)
(5^2 + 8^2 = 89)
(8^2 + 9^2 = 145)
(1^2 + 4^2 + 5^2 = 42)
(4^2 + 2^2 = 20)
(2^2 + 0^2 = 4)
… and it goes back to 4, forming a cycle.

By using the Tortoise and Hare approach:

The slow pointer will produce the sequence: 4, 16, 37, 58, …
The fast pointer will produce the sequence: 16, 58, 20, 4, …

After a few iterations, both the slow and fast pointers will meet, indicating a cycle. In this problem, detecting a cycle means the number is not happy.

Why it works:

Imagine a circular racetrack. If you have two runners - one running twice as fast as the other - they’ll eventually end up at the same position on the track, because the faster runner will catch up to the slower runner from behind.

Similarly, in the context of sequences, if there’s a cycle, the fast pointer (hare) will eventually meet the slow pointer (tortoise) inside the loop.

Conclusion:

Floyd’s Cycle Detection Algorithm is a powerful tool for detecting loops in sequences without needing to use extra space (like storing all seen elements in a set).

Get the sum of the squared digits

I learnt that we can use % to get the last digit of a number and / to get the rest of the digits. For example, if we want to get the last digit of 123, we can use 123 % 10 = 3. If we want to get the rest of the digits, we can use 123 / 10 = 12.

int getSum (int n){
    int sum = 0, digit;
    while (n != 0){
        digit = n % 10;
        sum += digit * digit;
        n = n / 10;
    }
    return sum;
}

Implementation of Floyd Cycle Detection Algorithm

bool isHappy(int n) {
    int slow = n, fast = n;
    do{ slow = getSum(slow);
        fast = getSum(getSum(fast));
        if (fast == 1)
            return true;
    }while(fast!=slow);
    return false;
}