C solution with 1000 boolean values to record results. (3ms with 400 test cases)


  • 4
    F

    if int has 4 bytes, then the biggest int will be roughly around 2 billion, so after the first process, the number will be less than 10 * 9 ** 2(e.g. 1,999,999,999 -> 730 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> ...), and it will be less than 10 * 9 ** 2 forever.

    So we can use a boolean table to record whether a number(which is less than 1000) has appeared. That is the key idea of my solution.

    Example: If we want to know whether 42 is a happy number. Since 42 -> 20, and the following process is 20 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 (20 appeared again! So a loop is detected). By the princeple of pigeon hole, we are sure the process will end with a loop (1 -> 1 is also a loop).

    In my program, I just use 1000 instead of 10 * 9 ** 2 for simplicity. In fact, 10 * 9 ** 2 boolean values are enough~

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

Log in to reply
 

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