# 4ms, 5 line C code

• Using fact all numbers in [2, 6] are not happy (and all not happy numbers end on a cycle that hits this interval):

``````bool isHappy(int n) {
while(n>6){
int next = 0;
while(n){next+=(n%10)*(n%10); n/=10;}
n = next;
}
return n==1;
}``````

• Can you explain why "all unhappy numbers end on a cycle that hits the interval [2, 6]"?

• Amazing... why?

• Aha, I see! Here is the proof of this proposition.

http://en.wikipedia.org/wiki/Happy_number#Sequence_behavior

• great job! But why?

• If a number is NOT happy, there is always a 4 in the cycle.

``````bool isHappy(int n) {
if (n <= 0) return false;

int magic = 4;
while (1) {
if (n == 1) return true;
if (n == magic) return false;
int t = 0;
while (n) {
t += (n % 10) * (n % 10);
n /= 10;
}
n = t;
}
}``````

• if n=2or3 , You can't exit the big loop....BTW, the "magic" is a good idea :))

• I tried 2 or 3, it does exit the big loop. You may want to try it yourself. :P

• Sorry, I miss forget n%10 and it will return after it XDD

• OMG, it's amazing !!! But why~ AHA

• from 1 to 9, only 1 and 7 are happy numbers

• Can't believe it!

• I don't think you could come up with this observation during the interview, is there are more generic approach?

• True; I found this by a little experimentation. However it can be easily shown that any number over 250 (or actually 200) will turn into a smaller number, so could just build a set of all such numbers and look for repeated ones.

• Uh...it's fantastic, but is it necessary to prove that any number would decrease down smaller than 6 at last, rather than getting into a circle of numbers all bigger than 6 (or even a circle of all 2-digit, 3-digit number) ?

• Oh...I see the link of proof on wiki...

• why are you so diao

• @runner_quan said in 4ms, 5 line C code:

why are you so diao

hahaha, maybe he cannot understand

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