# 5ms c++ solution using hashtable

• The common choice is to use map or set to check if there is a loop. since the maximum sum is no greater than 2x2 + 9x9x9 (2,999,999,999), we can use a 1000 lengh hashtable . It's not O(1) space but it's faster than the fast-slow pointer solution.

``````class Solution {
public:
int tran(int n){
int ans = 0;
while(n){
ans += pow(n%10, 2);
n/=10;
}
return ans;
}
bool isHappy(int n) {
bool rep[1000];
memset(rep, 0, sizeof(rep));
n = tran(n);
while(!rep[n]){
rep[n] = true;
if(n == 1)
return true;
n = tran(n);
}
return false;
}
};``````

• The same idea, but with C and less function call, so the following code run a little faster (3ms). I have posted it in another question already.
So I just pasted the code here (written by myself).

``````bool isHappy(int n) {
bool *bp = (bool *)calloc(1000, sizeof(bool));// in fact, 10 * 9 ** 2 space is enough
while(true){
int sum = 0;
for(;n;n /= 10){
int r = n % 10;
sum += r * r;
}
if(bp[n = sum]) // assign the value of sum to n, and test whether n has appeared.
break;
bp[n] = true;
}
free(bp);
return (n == 1);
}
``````

• INT_MAX=2,147,483,647, so max sum is no greater than 11+99*9(1,999,999,999).
Is it right?

• Yes~ Since INT_MAX = 2,147,483,647 < 9,999,999,999, I just wrote 1099 space is enough. But in fact, just as you said, 11+99*9 is already enough. Thank you. (To keep the program easy to understand, maybe we'd better employ an extra space. Thus, we will not always need to plus 1 or minus 1.)

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