“This is the second day of my participation in the First Challenge 2022.

Happy Number

.

Brush algorithm every day, happy? If you feel the pain of thinking hard and not being able to solve the problem, think more about the feeling after the breakthrough, think about the happiness of that moment and the transparent happiness after solving the problem, all the pain is temporary, everything will be bright. Today we are going to solve the problem: happiness number

LeetCode teleports 202. Happiness number

The title

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

Happiness number is defined as:

For a positive integer, replace the number each time with the sum of squares of the numbers at each of its positions. And then you repeat the process until the number is 1, or it could go on forever but it never gets to 1. If you can change it to 1, then that number is happiness. Return true if n is the happy number; If not, return false.

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



Input: n = 2
Output: false

Copy the code

Constraints:

• 1 <= n <= 231 - 1

Thinking line

Their thinking

This problem seems to be very complicated at first, but it is a familiar recipe and a familiar taste when carefully thinking about it.

Judge probability

First of all, let’s summarize and speculate on how many possible outcomes there are for this problem.

1. We are consistent in our search for happiness, and we get it1So this number is a happiness number. Example: 19 -> 82 -> 68 -> 100 -> 1 (Finding 1 means finding happiness)
2. If we’re stuck in a dead end, repeating the cycle of death in the search for happiness, then it’s not the happiness number. For example: 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4
3. In the search for happiness, the baggage grows, the numbers get bigger and bigger, and finally they approach infinity. It’s not something we can picture in our head. How do we prove that this exists? We’re looking for bigger and bigger numbers, so what’s the biggest number? It must be all the digits9So let’s make a table to calculate it

It is clear from the table that for a 3-digit number, it cannot be greater than 243. So that means that either it’s going to loop through 243 and get the result of case 2, or it’s going to get 1 as a happy number. For numbers with four or more digits, it quickly drops to three digits. So we know that the third scenario is impossible. We just have to deal with case one and case two.

The most intuitive way to do it

If there are only possibilities 1 and 2 above, how can we find the result quickly? We can use an array ARR to hold the values during the calculation

• If the final value becomes 1, the number proves to be a happy number, and returnstrue
• If the value is not 1 and appears in the array, the loop is entered. Instead of happiness number, returnfalse.
• If the value is not 1 and does not appear in the array, place the array in the array and continue the calculation.

Following the above steps, we can quickly get the following code

function isHappy(n: number) :boolean {
    const arr = [n];
    while(n ! = =1 ) {
        const find = findHappy(n);
        if(arr.includes(find)) return false;
        arr.push(find);
        n = find
    }

    return true;


};
function findHappy(n: number) :number {
    let res = 0;
    while (n > 0) {
        const f = n % 10;
        n = Math.floor(n / 10);
        res += f ** 2
    }
    return res;
}
Copy the code

Time complexity

O(log n)

Familiar smell

If only the above 1, 2 possibilities, we look, this is not the same as the circular list solution! , we can use the fast and slow pointer to quickly determine whether we have entered the cycle in the process of looking for happiness, so as to get whether the number is happiness number.

It’s worth noting

• The termination condition that we determine is that the fast pointer points1Corresponds to the direction in the circular listnull
• The occurrence condition of the cycle is still that the fast pointer and the slow pointer overlap, that is, the slow pointer that the fast pointer catches up with.

So we get the following code

function isHappy(n: number) :boolean {
    if(n === 1) return true;
    let slow = n;
    let fast = findHappy(n);

    while(fast ! = =1&& findHappy(fast) ! = =1) {
        if(fast === slow) return false;
        fast = findHappy(findHappy(fast))
        slow = findHappy(slow)
    }

    return true;


};
function findHappy(n: number) :number {
    let res = 0;
    while (n > 0) {
        const f = n % 10;
        n = Math.floor(n / 10);
        res += f ** 2
    }
    return res;
}
Copy the code

Time complexity

O(logn)

Use mathematical methods

This is something I found on the Internet, and it makes people say wow. We can see from the above analysis that if there is a ring, it must be within three digits, so it must be less than 243. That way we can find all the rings by force. We will find that within 243 there is only one ring, which is 4→16→37→58→89→145→42→20→4. All the other numbers are on the chain that goes into this loop, or on the chain that goes into 1.

And then we can get an algorithm that works out quickly.

function isHappy(n: number) :boolean {
    const cycle = [4.16.37.58.89.145.42.20];
    while(n ! = =1 && !cycle.includes(n)) {
        n = findHappy(n)
    }
    return n === 1

};

function findHappy(n: number) :number {
    let res = 0;
    while (n > 0) {
        const f = n % 10;
        n = Math.floor(n / 10);
        res += f ** 2
    }
    return res;
}
Copy the code

If we observe the rule of seeking happiness within 243, we can also find that the process of seeking happiness for each number always appears in the single digit, and only 1 and 7 are happy numbers in the single digit. All the others are non-happiness numbers. So we can also use this rule to determine quickly.

The following code

function isHappy(n: number) :boolean {

    while (n >= 10) {
        n = findHappy(n)
    }
    return n === 1 || n === 7

};

function findHappy(n: number) :number {
    let res = 0;
    while (n > 0) {
        const f = n % 10;
        n = Math.floor(n / 10);
        res += f ** 2
    }
    return res;
}
Copy the code

This is my solution to this question. If you have any questions or better solutions, please leave a comment and interact.