Use the same way as checking cycles in a linked list


  • 12
    M
    class Solution {
    public:
        bool isHappy(int n) {
            int A = nxt(n), B = nxt(nxt(n));
            while (A != 1 && A != B) {
                A = nxt(A);
                B = nxt(B);
                B = nxt(B);
            }
            return A == 1;
        }
    private:
        int nxt(int num) {
            int res = 0;
            while (num) {
                res += (num % 10) * (num % 10);
                num /= 10;
            }
            return res;
        }
    };
    

    Think the process as a linked list, then the code is easy to understand.


  • 2
    C

    It's a trade off here, you save the space for storing the processed numbers, but bring a bunch of duplicate operations.


  • 0
    M

    Very nice solution! It is not essential but we can check if(n==1) first. Thanks for the answer!


  • 0
    L

    what are the duplicate operations?


  • 0
    Y

    can you please tell us how this works? how it check a cycle occur. why there is two B = nxt(B)
    Thank you.


  • 0
    D

    I would say all the compute for the fast pointer (B). But also all the compute needed for full cycles of A and B before they meet.


Log in to reply
 

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