Why my solution does not work?


  • 0
    R
    class Solution {
    public:
        bool isHappy(int n) 
        {
            string digits = to_string(n);
            
            int total = 0;
            
            for (int i=0; i<digits.size(); ++i)
            {
                total += ((char)digits[i]-'0') * ((char)digits[i]-'0');
            }
            
            if (1 == total)
                return true;
            else 
                return isHappy(total);
        }
    };

  • 0
    Z
    This post is deleted!

  • 0
    F

    It's not amiguous. If the number is happy the sequence of operations will lead to a 1 and if the number is not happy the sequence will loop and never reach 1.


  • 0
    C

    If the number n is not a happy number, your solution will go into infinite loop. So definitely you'll get TLE.


  • 0
    M

    Happy numbers always converge to 1 and for the following iterations, the output will stay as 1.
    Eg:
    19 -> 82 -> 68 -> 100 -> 1 -> 1 -> 1 ...... stays at 1

    Unhappy numbers eventually enter a cycle which repeats.
    Eg:
    2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4

    Do you notice that the cycle repeats from 4 in the above example?


  • 2
    M

    Happy numbers always converge to 1 and for the following iterations, the output will stay as 1. Eg: 19 -> 82 -> 68 -> 100 -> 1 -> 1 -> 1 ...... stays at 1

    Unhappy numbers eventually enter a cycle which repeats. Eg: 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4

    Notice that the cycle repeats from 4 in the above example (an infinite loop).

    In your case, the recursive call you make in the else condition - it never ends..


  • 0
    R

    but why my solution cannot get it through? Thanks!


  • 0
    R

    yes, but an infinite loop also never ends, right? Correct me, if I am wrong. Thanks.


  • 0
    C

    mithmatt gives a pretty good example which you may refer to.


  • 0
    C

    Yes, so your program will never finish if the test data is not a happy number. The test runner will time out and you get TLE.


  • 0
    M

    yes, the loop never ends


  • 0
    R

    Thanks. I think I had a confusion for this problem. Although loop never ends, program should return finally to tell if the input number is a happy number or not. Thank you so much!


  • 0
    C

    so to correctly do this problem, we need to create a table that stores the previous value and check every time if the new result is in the table?


Log in to reply
 

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