Easy C++ solution


  • 0
    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;
        }
    };
    

  • 0

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


  • 1

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


  • 1

    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?


  • 0

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


  • 0

    @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:
    		seen.add(n)
    		n = sum(int(d)**2 for d in str(n))
    	return len(seen)
    
    >>> max(map(steps, range(1000)))
    19
    

  • 0

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


  • 0

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


Log in to reply
 

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