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;
}
};
Easy C++ solution


@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 withfind
.

@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 tripledigits, 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: seen.add(n) 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 asset
!(Added that to my above statistics.)
