Leetcode-202. happy number

Mathematical problems

---

Topic details

Write an algorithm to judge a number n Is it a happy number .
「 Happy number 」 Defined as ：
For a positive integer , Replace the number with the sum of the squares of the numbers in each of its positions .
Then repeat the process until the number becomes 1, It could be Infinite loop But it doesn't change 1.
If this process The result is 1, So this number is the happy number .
If n yes Happy number Just go back to true ; No , Then return to false .

---

Example 1：

 Input ：n = 19
 Output ：true
 explain ：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:

 Input ：n = 2
 Output ：false

Ideas :
The first idea of this problem is to find the sum of the squares of the digits in a circular way , Utilize collection storage , If you find 1 Just go back to true, Find the saved sum of squares and return false

My code ：

class Solution 
{
    
public:
    //  Auxiliary function   Find the sum of the squares of the digits 
    int getSum(int n)
    {
    
        int sum = 0;
        while (n)
        {
    
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    //  The main function 
    bool isHappy(int n) 
    {
    
        int sum = 0;
        unordered_set<int> set;
        while (true)
        {
    
            sum = getSum(n);
            if (sum == 1) return true; //  Loop found 1 Just go back to true
            //  The loop returns when it finds a repetition false
            if (set.find(sum) != set.end()) return false;
            // Otherwise, it will be deposited in sum Post update n Continue to cycle 
            set.insert(sum);
            n = sum;
        }
    }
};

When writing the first method, we can find , In fact, we are constantly looking for specified elements in a loop , We can think of a good way to find elements in the circular linked list : Fast and slow pointer method !
That is, define the slow pointer slow The slow pointer is initially on the first node , Quick pointer fast Initially on the second node , then slow One step at a time ,fast Take two steps at a time , until fast find 1(true) perhaps fast and slow meet ( No dead cycle found false) The code is as follows :

class Solution 
{
    
public:
    //  Auxiliary function   Find the sum of the squares of the digits 
    int getSum(int n)
    {
    
        int sum = 0;
        while (n)
        {
    
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    //  The main function 
    bool isHappy(int n) 
    {
    
        // initialization 
        int slow = n;
        int fast = getSum(n);
        //  Did not find 1  Don't meet   Just cycle 
        while (fast != 1 && slow != fast)
        {
    
            slow = getSum(slow);// Take one step 
            fast = getSum(getSum(fast));// Perform two steps 
        }
        return fast == 1; // Finally, jump out of the loop and see fast Is it right? 1
        
    }
};

Finally, there is another method that can be solved by mathematical laws , When the sum of squares of each bit of a number cannot be cycled into 1, Then it must fall into the cycle :4→16→37→58→89→145→42→20→4
According to this rule, we can write the following code :

class Solution 
{
    
public:
    //  Auxiliary function   Find the sum of the squares of the digits 
    int getSum(int n)
    {
    
        int sum = 0;
        while (n)
        {
    
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    unordered_set<int> set{
    4, 16, 37, 58, 89, 145, 42, 20};// initialization 
    //  The main function 
    bool isHappy(int n) 
    {
       //  Did not find 1 set I can't find ( Not falling into the dead circle )
        while (n != 1 && set.find(n) == set.end()) 
        {
    
            n = getSum(n); // Just go ahead 
        }
        return n == 1;
        
    }
};