Number of happiness

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

Happiness number definition:

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.

Example 1:

Input: n = 19 Output: true Description: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1Copy the code

Example 2:

Input: n = 2 Output: falseCopy the code

Ideas:

Possible scenarios:

  1. You end up with a 1
  2. Repeat numbers appear and enter the loop
  3. The value continues to grow, not cyclic, not 1.

If it’s a happiness number, we just keep going to the next value until we get to 1. If it’s not the happiness number, there could be 2,3.

If you test 999, you will find that the next digit of 999 is 243. Therefore, it can be seen that the next value of the input value cannot exceed 81*n. N is the number of digits. And because integers in a finite range must be finite, they must eventually lead to repetition and loops. The happiness number is just one of the special cases.

Through analysis, we found that the analysis process of happiness number is almost the same as that of judging circular linked list, only 1 is used instead of NULL. Therefore, the following calculation method can be obtained.

code

function isHappy(n: number) :boolean {
    let slow = n,fast = getNext(n);
    while(fast! = =1&& fast ! == slow){ slow = getNext(slow); fast = getNext(getNext(fast)); }return fast === 1;
}
function getNext(n:number){
    let next = 0;
    while(n){
        next += (n%10) * *2;
        n = Math.floor(n/10);
    }
    return next;
}
Copy the code