Beat 90% Fast Easy Understand Java Solution with Brief Explanation


  • 95
    M

    The idea is to use one hash set to record sum of every digit square of every number occurred. Once the current sum cannot be added to set, return false; once the current sum equals 1, return true;

    public boolean isHappy(int n) {
        Set<Integer> inLoop = new HashSet<Integer>();
        int squareSum,remain;
    	while (inLoop.add(n)) {
    		squareSum = 0;
    		while (n > 0) {
    		    remain = n%10;
    			squareSum += remain*remain;
    			n /= 10;
    		}
    		if (squareSum == 1)
    			return true;
    		else
    			n = squareSum;
    
    	}
    	return false;
    
    }

  • 0
    M

    Hi.

    May I ask why "the current sum cannot be added to set"? Because it's the repeated element?

    Thanks for anyone's response.


  • 0
    M

    got it. It's determined by boolean add() method in HashSet


  • 0
    N

    is this applied because in java duplicate key in not allowed in hashset?


  • 7
    M

    Absolutely right. In hash set and hash map, Java first use object's hashCode() function to compute the "slot" for the key. If two keys have the same hash code (this is called hash collision and it's actually very rare to happen), they will be compared by using the second key's equals() method, if return true, the two keys are exactly the same, the key will not be added(in set) or its value will be overwritten(in map); if return false, Java will create a linear chain in the slot to store both of them.


  • 0
    N

    Thanks a lot!


  • 1
    E

    For those who might be interested, Here is my proof of why such an algorithm is mathematically valid in the first place.


  • 1
    R

    your solution is brilliant . my idea is corollary of yours

    i just look for the 1 to 100 numbers and found only 20 numbers as happy number. this leads up to this clear solution.
    as sum of digits reduces and becomes less than 100 i can check this sum with my stored 20 numbers ..

    set<int>HappyNum = {1,7,10,13,19,23,28,31,32,44,49,68,70,79,82,86,91,94,97,100};
        bool isHappy(int n) {
               int sum=0;
               while(n){                     //finding sum of square of digits
                   sum+=(n%10)*(n%10);
                   n/=10;
               }
               if(sum<=100){                // if sum becomes less then 100 check --> is this in HappyNumbers set?     
                    if(HappyNum.find(sum)!=HappyNum.end())return true;
                    return false;
               }
               return isHappy(sum);
        }
    

  • 0

    The false condition for "while (inLoop.add(n))" is squareSum == a previous added element in hashset. How can we know it must have a squareSum == a previous added n ?


  • 0
    M

    Actually it doesn't have to have a squareSum == a previous added element. This algorithm strictly reflects the process. Try some test cases and you will get it.


  • 0
    A

    @mihoherbal once meet repeated element , the num is not the happy number because it will never end ,so ,in the end ,the function must return false;


  • 0
    L

    Same idea. Shorter code:

        public boolean isHappy(int n) {
            Set<Integer> set = new HashSet<>();
            for (int next; set.add(n) && n != 1; n = next) {
                for (next = 0; n > 0; n /= 10) {
                    next += Math.pow(n % 10, 2);
                }
            }
            return n == 1;
        }
    

  • 0
    Z

    is there any number which would fill in the set with HUGE different numbers? if the answer is yes, the algorith is not practical (as it consumes too much memory).

    BTW:
    I came up with similiar solution, but I resume the number would be changed to its original value, thus only use a variable to check if it equals to original value ot check loop. ended up with TLE.


  • 0

    Hello, similar solution like yours with space(1); We could try to enumerate to prove that in the endless loop of happy number, it always has 1,4 or 9. So continue the loop, once these numbers show up. There you go~

    public boolean isHappy(int n) {
            if(n==0)
                return false;
            while(true){
                int r = 0;// r is the temp number to store square of digits
                int digit = 0;// each digits in a number
                if(n==1){
                    return true;
                }else if(n==4||n==9){
                    return false;
                }else{
                    while(n>0){
                        digit = n % 10;
                        r += digit*digit;
                        n /= 10;
                    }
                    n = r;//  next number to be computed
                }
            }
        }
    

  • 0
    Y

    Nice solution! Could anybody please let me know how to calculate the time and space complexities of the solution? Thanks.


  • 0

    Recursive. Unlike other integer exponentiation problems, this problem has no overflow concerns. It breaks down the integer into single digits, and square them individually.

        Set<Integer> set = new HashSet<>(); 
        public boolean isHappy(int n) {
            if (set.contains(n)) return false; 
            set.add(n); 
            
            String str = String.valueOf(n); 
            char[] chars = str.toCharArray(); 
            int sum = 0, pow = 0; 
            for (char c : chars) {
                pow = (int)Math.pow(Character.getNumericValue(c), 2); 
                sum += pow;  
            }
            if (sum == 1) return true; 
            return isHappy(sum); 
        }

  • 0
    N

    @rakesh_joshi how did you get the HappyNum set?


  • 0
    J

    I am confused about the what the time complexity of this code?
    Thanks a lot.


  • 0
    C

    Share my simple logic here:

       public boolean isHappy(int n) {
            Set<Integer> set = new HashSet<>();
            while(getSquareSum(n) != 1){
                 n = getSquareSum(n);
                if(!set.add(n))return false; 
            }
            return true;
        }
        
        private int getSquareSum(int n){
            int result = 0;
            while(n != 0){
                result += Math.pow(n%10,2); 
                n = n/10;
            }
            return result; 
        }
    

  • 0
    L

    I didn't understand why use set as a judge condition, because i think the outcomes of every turns won't repeat. If appear repeated, can i think of in an infinite loop has been running for many rounds. Who can helpt me to explain it? Thx!


Log in to reply
 

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