Simple Java solution without extra space


  • 0
    J

    Here is an accepted iterative solution that uses constant space.

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

  • 0
    L

    Can you explain why it works please ? thanks!


  • 0
    D

    I don't think this works. Try 7.


  • 0
    J

    Yes you are entirely correct the sequence for 7 is:
    49, 97, 130, 10

    Despite that the solution has been accepted:

    400 / 400 test cases passed.
    Status: Accepted
    Runtime: 247 ms

    So there are not all edge cases covered by this tests.


  • 0
    D

    Actually yours is very clever/smart solution. Just change the return statement to "return number == 1 || number == 7;". I have proved (by enumeration) that all happy paths will contain a number below 10 and for all numbers below 10 only 1 and 7 are happy numbers.

    How did you come with the solution, though? It's easy to prove but hard to think/guess that way.


  • 0
    J

    I wonder if there is a more mathematically inclined person that could prove that what I have found through running the experiments:

    I did focus on the values from range <1, 9> and by running the experiments I came up with fallowing conclusions:

    The only acceptable sequences will be those that will sum up to the power of ten:
    1, 10, 100, 1000 ...

    The sequence for 2 will be the same as for 4 = 2 * 2, similary 3 and 9 = 3 * 3 by running the tests it turns out that 2 cycles through itself:

    2: 2, 4, 16, 37, 58, 89, 145, 42, 20, 2

    And even 3 cycles through 2:
    3: 3, 9, 81, 65, 61, 37, 58, 89, 145, 42, 20, 2

    The same is true for 5:
    5: 25, 29, 85, 89, 145, 42, 20, 2

    And as dan_li spotted above the only exception to that is 7.

    The hardest part was to convince yourself that any number has to cycle through the value in ranges <1, 9>.

    I wonder if someone knows some mathematic proof towards this observation.


  • 0
    I

    I came up with the shorten version of that idea:

    public bool IsHappy(int n) {        
        bool result = false;
        int summ = 0;
        while ( n > 0) {
            int tmp = n % 10;
            summ = summ + (tmp*tmp);
            n = (n - tmp)/10;
        }
        if (summ >= 10)
        {
            return IsHappy(summ);
        }
        
        return (summ == 1);
    }
    

Log in to reply
 

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