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

The happy number is defined as replacing a positive integer each time with the sum of squares of the numbers in 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.Copy the code
Example 1: Input: n = 19 Output: true Description: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1 Example 2: Input: n = 2 Output: falseCopy the code

I thought happy count would be happy to see him.

Resolution:

According to the definition of a happy tree, a happy tree is the sum of each digit of a positive integer (ten million… Square the sum to form a new number, and do the same again until the number is 1. We can assume that if this number is not a happy number, then this operation will go on and on, in an infinite loop! So it can be known that:

  • The underlying logic and criteria for the happiness tree is whether the operations are infinite, or if you end up with a number of 1.
  • Since it is infinite, it must intersect. That is to say, the same number will appear at least twice, causing the process to repeat, and then there is an infinite loop.

Conclusion: Judge whether it is a happy number, that is, judge whether the sum of squares operation will have an intersection or get 1

Break down:

First write an algorithm to get the sum of squares of each digit of an integer:

const getNumber = (n) => {
    let res = 0
    do {  
        const a = n % 10
        n = (n - a) / 10
        res += a * a
    } while( n >= 10)
    res += n * n
    return res
}
Copy the code

PS: There have been attempts to convert integers into arrays of strings and then square and add each element separately, but the performance is lower than integer computation.

How do you know where it intersects and whether it’s going to be 1 each time?

If it is 1, then it is the happiness number. Eturn true. If not, store the number in an array and proceed with getNumber(). After each operation, 1 is checked and the array is checked to see if that number exists. If so, it intersects. Return false

/** * @param {number} n * @return {boolean} */ const getNumber = (n) => { let res = 0 do { const a = n % 10 n = (n - a) / 10 res += a * a } while( n >= 10) res += n * n return res } var isHappy = function(n) { let list = [] while(true) { n = getNumber(n) if (n === 1) { return true } else if (list.indexOf(n) ! == -1) { return false } list.push(n) } };Copy the code

The above can complete the judgment of happiness number.

So what if I don’t want to create a new array to solve this problem?

If you want to determine whether a chain is circular, you can also consider using the two-pointer tortoise and rabbit algorithm to solve the problem. Here do not do too much introduction, can refer to the previous article two-pointer tortoise and rabbit race to determine whether the linked list ring

Tortoise and rabbit race algorithm:

/** * @param {number} n * @return {boolean} */ const getNumber = (n) => { let res = 0 do { const a = n % 10 n = (n - a) / 10 res += a * a } while( n >= 10) res += n * n return res } var isHappy = function(n) { let slow = getNumber(n) let quick = getNumber(getNumber(n)) if (quick === 1) { return true } while(slow ! == quick) { slow = getNumber(slow) quick = getNumber(getNumber(quick)) console.log({quick}) if (quick === 1) { return true } } return false };Copy the code