My Easy-to-Understand, No-Magic-Number solution in C and Python


  • -1
    L

    A lot of solutions I've seen so far either uses some sort of "Magic" number (which is impractical in real interviews because you wouldn't have unlimited time for observation or access to wikipedia), or uses very language specific features, so I decided to code up a general approach in both C and Python.

    Here it goes:

    C:

    bool isHappy(int n) {
        
        while (n >= 1) {
    
            int res = 0; 
    
            while ((n / 10) >= 1) {
                res += (n % 10) * (n % 10);
                n /= 10;
            }
            
            n = res + (n % 10) * (n % 10);    
            
            if (n == 1) return true;
            else if (n < 10) return false;
        }
        
        return false;
    }
    

    Python:

    class Solution(object):
        def isHappy(self, n):
            """
            :type n: int
            :rtype: bool
            """
            
            while (n >= 1):
                res = 0
                
                while ((n / 10) >= 1):
                    res += (n % 10)*(n % 10)
                    n /= 10
    
                n = res + (n % 10)*(n % 10)
                
                
                if (n == 1):
                    return True
                elif (n < 10):
                    return False
    
            return False

  • 0

    Complaining about magic numbers and then you do if (n < 10) return false; yourself?

    You should fix your title.


  • 0
    L

    I don't think 10 is a "magic number" in this case, after all calculations and if you get a number less than 10 but not equal to 1, that means the input "n" is not a happy number, hence return False directly.


  • 0
    K

    And why " if you get a number less than 10 but not equal to 1, that means the input "n" is not a happy number" ?


  • 0
    L

    I think you guys are right, 10 does seem to be yet another magic number. Closing this post ...


  • 0

    Besides what kk262777 said, there's also the magic of why every number eventually ends up under 10. (If there were a cycle above 10, your solution would never stop.)


  • 0
    K

    n < 10 kind of make sense, however, I can't prove its correctness. To prove this solution is correct, we have to prove: if the number falls in [2,9], it will never become 10, 100, 1000... or 1.


  • 0

    After reading the wiki, I think there will always be number less than 10 during the searching. The wiki page proved that it will fall into 1-100. After brute force iterate, it's proved. Only 1 and 7 are happy number.


  • 0

    It's actually wrong, fails Indream's test case 1111111.


Log in to reply
 

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