Java solution, 2 ms, without using Set, beat 84%


  • 0
    C

    I think the important part is how to end a potential infinite loop. Some suggest using Set, it is a straight forward solution, but I found it will increase the time cost. Therefore, I use another condition to detect an infinite loop, which is a bit tricky though.

    public class Solution {
        public boolean isHappy(int n) {
           
        if ( n < 5) {
            if (1 == n)
                return true;
            else
                return false;
        } 
            
        int sum = 0;
        
        while ( n >= 10) {
            sum += (n % 10) * (n % 10);
            n = n / 10;
        }
        sum += n * n;
        
        return  isHappy(sum);
        }
    }
    

  • 0
    H

    @CHYGO same idea here, but I eventually give up this method since I can't even mathematically prove that for every number, the sum is gonna fall below 10, not even to mention 5.


  • 0
    N

    I had the same performance with below. The exit is based on the fact that converge (if its going to happen) seems to occur within 5 iterations for numbers that don't overflow int.

    public class Solution {
        boolean isHappy(int n) {
           return isHappy(n, 0);
        }
        
        boolean isHappy(int n, int depth) {
           if (n == 1) return true; 
           if (n == 0 || depth> 5) return false;
           
           int sum = 0;
           while(n > 0)
           {
               int d = (n%10);
               sum += d*d;
               n/=10;
           }
           return isHappy(sum, depth+1);
        }
    }
    

  • 0
    Y

    @noah.s.moore How can you prove that if the depth is greater than 5,then return false?


Log in to reply
 

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