# My solution in C( O(1) space and no magic math property involved )

• I see the majority of those posts use hashset to record values. Actually, we can simply adapt the Floyd Cycle detection algorithm. I believe that many people have seen this in the Linked List Cycle detection problem. The following is my code:

``````int digitSquareSum(int n) {
int sum = 0, tmp;
while (n) {
tmp = n % 10;
sum += tmp * tmp;
n /= 10;
}
return sum;
}

bool isHappy(int n) {
int slow, fast;
slow = fast = n;
do {
slow = digitSquareSum(slow);
fast = digitSquareSum(fast);
fast = digitSquareSum(fast);
} while(slow != fast);
if (slow == 1) return 1;
else return 0;
}``````

• This is a nice one! :)

• Just like two pointers in linked list cycle, good job.

• I ended up with the same idea, in c++

``````  int next(int n)
{
int res=0;
while (n)
{
int t = n % 10;
res += t*t;
n/=10;
}
return res;
}

bool isHappy(int n)
{
int i1=n, i2=next(n);

while ( i2 != i1)
{
i1 = next(i1);
i2 = next(next(i2));
}

return i1==1;
}``````

• excellent idea

• Just curious...how do you know for sure that the fast pointer we loop back and catch up to the slow pointer?

• Figured it out! If it is a happy number than it will stay at one and the slow pointer will eventually catch up. On the other hand, there must be a recurring number (that's why we need a hashset.)

• really awesome!!!!!!!!!!!!clever

• Very clever idea. Whether the number is or not, its square sum sequence is always a list with cycle.

• why is the square sum sequence be a cycle?

• This is nicer :)

• Really great idea to apply the algorithm for detecting cycle in linked lists. Well, the codes can be simplified a little. The last two lines of `isHappy` can just be simplified to `return slow == 1;`. BTW, writing `fast = digitSquareSum(fast);` twice may not be a good idea (duplicate codes), why not write `fast = digitSquareSum(digitSquareSum(fast));`?

• Well, this code looks more similar to Linked List Cycle :-)

• Nice idea, but it seems that if n is a happy number, definitely `fast` will turn to 1 first, which means in this case, your code will take one time more loops than it should be, because you have to wait the `slow` turning to 1 as well. So I made a little simplification.

``````    int digitSquareSum(int n) {
int sum = 0, tmp;
while (n) {
tmp = n % 10;
sum += tmp * tmp;
n /= 10;
}
return sum;
}

bool isHappy(int n) {
int slow, fast;
slow = fast = n;
do {
slow = digitSquareSum(slow);
fast = digitSquareSum(fast);
fast = digitSquareSum(fast);
if(fast == 1) return 1;
} while(slow != fast);
return 0;
}``````

bool isHappy(int n)
{
map<int, int> mHappyNum;
while (1)
{
mHappyNum[n] = 1;
int iTmp = calcSquare(n);
if (1 == n)
{ return 1; }
if (!mHappyNum.count(iTmp))
{ n = iTmp; }
else
{ return 0; }
}
return 0;
}
int calcSquare(int n)
{
int sum = 0;
while (n > 10)
{
int iDigit = n % 10;
sum += iDigit * iDigit;
n /= 10;
}
sum += n * n;
return sum;
}

• @autowonderman, formatting your code is essential to make others willing to read it.

• autowonderman, it's C not C++solution

• Why will the while loop break when the number is not happy?

• I don't quite understand why it works. Can you explain it? Thank you!

• What is the complexity of this solution?

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