4 C++ Solutions with Explanations


  • 12
    A

    Well, there may be so many solutions for this problem. Here are 4 suggested solution for this problem, two based on hash and the other based on cycle detection algorithm.


    hash-set

    The hash-set solution is very straightforward. For every new data, we check whether it is already in the set. If no, we insert it into the set. If yes, we detect the loop. Only when the node in the loop is "1", the number is happy number.

    The code is as follow. The time complexity is O(nlogn) (due to the sort function).

    class Solution {
    public:
        bool isHappy(int n) {
            unordered_set<int> tmp;
            
            while(n != 1)
            {
                if(tmp.find(n) == tmp.end())
                    tmp.insert(n);
                else
                    return false;
                
                int sum = 0;
                while(n != 0)
                {
                    sum += pow(n % 10,2);
                    n = n / 10;
                }
                
                n = sum;
            }
            
            return true;
        }
    };
    

    hash-map

    The idea is similar as hase-set. We check the node value to check whether it is in the loop.

    The code is as follow. The time complexity usually is O(1) (the worst may be O(n) due to conflict)

    class Solution {
    public:
        bool isHappy(int n) {
            unordered_map<int,int> tmp;
            
            while(n != 1)
            {
                if(tmp[n] == 0)
                    tmp[n]++;
                else
                    return false;
                
                int sum = 0;
                while(n != 0)
                {
                    sum += pow(n % 10,2);
                    n = n / 10;
                }
                
                n = sum;
            }
            
            return true;
        }
    };
    

    Floyd's Cycle detection algorithm

    Floyd's cycle detection algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. Obviously, if there is a loop, they will meet in the loop. It is also called the "tortoise and the hare algorithm"

    The code is as follows, which should be self-explanatory. The time complexity is O(λ + μ)*.

    class Solution {
    public:
        int next(int n)
        {
            int sum = 0;
            
            while(n != 0)
            {
                sum += pow(n % 10,2);
                n = n / 10;
            }
            
            return sum;
        }
    
    public:
        bool isHappy(int n) {
            int slow = next(n);
            int fast = next(next(n));
            
            while(slow != fast)
            {
                slow = next(slow);
                fast = next(next(fast));
            }
            
            return fast == 1 ;
        }
    };
    

    Brent's Cycle detection algorithm

    Brent's algorithm features a moving rabbit and a stationary, then teleporting, turtle. Both turtle and rabbit start at the top of the list. The rabbit takes one step per iteration. Every once in a while, we teleport the turtle to the rabbit's position, and let the rabbit continue moving. We start out waiting just 2 steps before teleportation, and we double that each time we move the turtle. If there is a loop, they will meet in the loop.

    The code is as follows. The time complexity is O(λ + μ)*. However you're doing less stepping than with Floyd's (in fact the upper bound for steps is the number you would do with Floyd's algorithm). According to Brent's research, his algorithm is 24-36% faster on average for implicit linked list algorithms.(However, it cost same time as the Floyd's in the OJ ;) )

    class Solution {
    public:
        int next(int n)
        {
            int sum = 0;
            
            while(n != 0)
            {
                sum += pow(n % 10,2);
                n = n / 10;
            }
            
            return sum;
        }
    
    public:
        bool isHappy(int n) {
            int slow = n;
            int fast = next(n);
            int cnt = 1;
            int lim = 2;
            
            while(slow != fast)
            {
                if(cnt == lim)
                {
                    cnt = 1;
                    lim = lim*2;
                    slow = fast;
                }
                else
                    cnt ++;
            
                fast = next(fast);
            }
            
            return fast == 1 ;
        }
    };
    

    P.S.
    *If you want more detailed explanation for the two algorithm, you can find it in https://en.wikipedia.org/wiki/Cycle_detection


  • 1
    X

    great code! But can you explain why the time-complexity of hash-set solution is O(nlgn)? where is the sort function?
    Why the hash-map solution is O(1) (worst O(n))? Because I think those two solutions are almost identical in time complexity.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.