# Simple Java solution without extra space

• 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;
}
}``````

• Can you explain why it works please ? thanks!

• I don't think this works. Try 7.

• 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.

• 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.

• 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.

• 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);
}
``````

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