My solution in C( O(1) space and no magic math property involved )


  • 465
    F

    I see the majority of those posts use hashset to record values. Actually, we can simply adapt the Floyd Cycle detection algorithm. I believe that many people have seen this in the Linked List Cycle detection problem. The following is my code:

    int digitSquareSum(int n) {
        int sum = 0, tmp;
        while (n) {
            tmp = n % 10;
            sum += tmp * tmp;
            n /= 10;
        }
        return sum;
    }
    
    bool isHappy(int n) {
        int slow, fast;
        slow = fast = n;
        do {
            slow = digitSquareSum(slow);
            fast = digitSquareSum(fast);
            fast = digitSquareSum(fast);
        } while(slow != fast);
        if (slow == 1) return 1;
        else return 0;
    }

  • 4
    G

    This is a nice one! :)


  • 3
    L

    Just like two pointers in linked list cycle, good job.


  • 40
    R

    I ended up with the same idea, in c++

      int next(int n)
        {
            int res=0;
            while (n)
            {
                int t = n % 10;
                res += t*t;
                n/=10;
            }
            return res;
        }
        
        bool isHappy(int n)
        {
            int i1=n, i2=next(n);
            
            while ( i2 != i1)
            {
                i1 = next(i1);
                i2 = next(next(i2));
            }
            
            return i1==1;
        }

  • 1
    Y

    excellent idea


  • 6
    I

    Just curious...how do you know for sure that the fast pointer we loop back and catch up to the slow pointer?


  • 8
    I

    Figured it out! If it is a happy number than it will stay at one and the slow pointer will eventually catch up. On the other hand, there must be a recurring number (that's why we need a hashset.)


  • 0
    C

    really awesome!!!!!!!!!!!!clever


  • 0
    S

    Very clever idea. Whether the number is or not, its square sum sequence is always a list with cycle.


  • 0
    C

    why is the square sum sequence be a cycle?


  • 0
    V

    This is nicer :)


  • 7

    Really great idea to apply the algorithm for detecting cycle in linked lists. Well, the codes can be simplified a little. The last two lines of isHappy can just be simplified to return slow == 1;. BTW, writing fast = digitSquareSum(fast); twice may not be a good idea (duplicate codes), why not write fast = digitSquareSum(digitSquareSum(fast));?


  • 0

    Well, this code looks more similar to Linked List Cycle :-)


  • 43
    R

    Nice idea, but it seems that if n is a happy number, definitely fast will turn to 1 first, which means in this case, your code will take one time more loops than it should be, because you have to wait the slow turning to 1 as well. So I made a little simplification.

        int digitSquareSum(int n) {
            int sum = 0, tmp;
            while (n) {
                tmp = n % 10;
                sum += tmp * tmp;
                n /= 10;
            }
            return sum;
        }
        
        bool isHappy(int n) {
            int slow, fast;
            slow = fast = n;
            do {
                slow = digitSquareSum(slow);
                fast = digitSquareSum(fast);
                fast = digitSquareSum(fast);
                if(fast == 1) return 1;
            } while(slow != fast);
             return 0;
    }

  • 0
    A

    what about map
    bool isHappy(int n)
    {
    map<int, int> mHappyNum;
    while (1)
    {
    mHappyNum[n] = 1;
    int iTmp = calcSquare(n);
    if (1 == n)
    { return 1; }
    if (!mHappyNum.count(iTmp))
    { n = iTmp; }
    else
    { return 0; }
    }
    return 0;
    }
    int calcSquare(int n)
    {
    int sum = 0;
    while (n > 10)
    {
    int iDigit = n % 10;
    sum += iDigit * iDigit;
    n /= 10;
    }
    sum += n * n;
    return sum;
    }


  • 2

    @autowonderman, formatting your code is essential to make others willing to read it.


  • 0
    4

    autowonderman, it's C not C++solution


  • 1
    Y

    Why will the while loop break when the number is not happy?


  • 1
    L

    I don't quite understand why it works. Can you explain it? Thank you!


  • 0
    N

    What is the complexity of this solution?


Log in to reply
 

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