C++ sol use hash table to detect cycle


  • 0
    M

    To solve this problem we need to know how to detect cycles. For example, n=a (a>0), and it may evolve like this: a -> b -> c -> d -> e -> f ->g ->... forever and will not become 1 (unhappy). To detect cycle a brute force idea is jus use an unordered_set to save all the numbers a, b, c, d,... along the way. Once you find a repeated number, say you have the sequence: a -> b -> c -> d -> c, then you know this number is unhappy.

    The code:

    bool isHappy(int n) {
            unordered_set<int> nums;
            while(n != 1) {
                if(nums.find(n)!=nums.end()) break;
                nums.insert(n);
                int sum = 0;
                while(n > 0) {
                    int y = n%10;
                    sum += y*y;
                    n/=10;
                }
                n = sum;
            }
            return n==1;
        }

Log in to reply
 

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