5ms c++ solution using hashtable


  • 14
    I

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

  • 0
    F

    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);
    }
    

  • 0
    F

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


  • 0
    F

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


Log in to reply
 

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