# Easy C++ solution

• class Solution {
public:
bool isHappy(int n) {
map<int, bool> map;
int source = n;
if(n==0) return false;
int sum = 0;
while(true){
while(n>0){
sum += pow(n%10, 2);
n = n/10;
}
if(sum==1) return true;
else if(map[sum]) return false;
else{
map[sum] = true;
n = sum;
sum = 0;
}
}
return false;
}
};

• @xiaozhuai

Keep in mind map sorts upon entry so it takes O(log(n)) time per insertion. Consider using an unordered_map to speed up insertion, or even unordered_set if all you need is to check for existence.

• @Ayamin I just tried it with this wrapper:

bool isHappy(int n) {
int count = 0;
for (int i=0; i<100; i++)
count += realIsHappy(n);
return count / 100;
}
bool realIsHappy(int n) {
(actual solution)
}

Submitted each version three times:

map:            326, 323, 379  =>  343 ms average
unordered_map:  359, 346, 369  =>  358 ms average
unordered_set:  319, 359, 342  =>  340 ms average
set:            292, 272, 259  =>  274 ms average
vector:         132, 149, 139  =>  140 ms average

The vector is unsorted, I just push the current sum to the back and I check with find.

• Ok I just added set to my tests. As you can see, it's significantly the fastest. Faster than unordered_set, too. So what's up with that?

• @StefanPochmann

Strange. Perhaps the STL implementation of the red-black tree that backs the set is somehow faster than the unsorted versions in certain cases.

• @Ayamin Yeah, I think set can be faster if it's small. Which it will be here, because the number of iterations will be small. I mean, even if you start with 1999999999, the next number will already be only 730. And once you're in the triple-digits, you can never escape, as even 999 leads to only 243. So at most ~243 iterations, and actually at most 19 or so (might be off by 1, depends on how you're counting):

>>> def steps(n):
seen = set()
while n not in seen:
n = sum(int(d)**2 for d in str(n))
return len(seen)

>>> max(map(steps, range(1000)))
19

• @Ayamin Oh haha... like I just showed, it'll be at most 20 iterations or so. So I just tried an unsorted vector. It's twice as fast as set!

(Added that to my above statistics.)

• @Ayamin Yeah, thank you, I will keep in mind what you said.

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