No hashset, O(1) time check whether is in the loop with mathematical proof


  • 14
    T

    class Solution {
    public:
    int loop[8] = {4,16,37,58,89,145,42,20};

    bool inLoop(int n){
        for(auto x: loop){
            if(x == n) return true;
        }
        return false;
    }
    
    bool isHappy(int n) {
        if(n == 1) return true;
        if(inLoop(n)) return false;
        int next = 0;
        while(n){
            next += (n%10)*(n%10);
            n /= 10;
        }
        return isHappy(next);
    }
    

    };

    proof:

    1.loop number is less than 162.

    Assume f(x) is the sum of the squares of x's digits. let's say 0 < x <= 9,999,999,999 which is larger than the range of an int. f(x) <= 9^2 * 10 = 810. So no mater how big x is, after one step of f(x), it will be less than 810.The most large f(x) value (x < 810) is f(799) = 211. And do this several times: f(211) < f(199) = 163. f(163) < f(99) = 162. So no mater which x you choose after several times of f(x),it finally fall in the range of [1,162] and can never get out.

    2.I check every unhappy number in range of [1,162] , they all fall in loop {4,16,37,58,89,145,42,20} ,which means every unhappy number fall in this loop.


  • 0
    L

    Great point! Those magic numbers lead to the endless cycle.

    Based on your answer, I made a few modifications with a 256-bit mask set for quick looking up.

    Here is my code:

    static inline void hash_set(int hash[], int n) {
        hash[n / 8] |= 1 << (n % 8);
    }
    
    static inline bool hash_has(int hash[], int n) {
        return ((hash[n / 8] >> (n % 8)) & 0x01) == 1;
    }
    
    bool isHappy(int n) {
        static int hash[32] = { 0xff, 0 };
        int next = 0;
    
        if (n == 0) return false;
    
        if (hash[0] == 0xff) {
            hash[0] = 0;
            hash_set(hash, 4);
            hash_set(hash, 16);
            hash_set(hash, 37);
            hash_set(hash, 58);
            hash_set(hash, 89);
            hash_set(hash, 145);
            hash_set(hash, 42);
            hash_set(hash, 20);
        }
    
        while (true) {
            next = 0;
            while (n) {
                next += (n % 10) * (n % 10);
                n /= 10;
            }
            if (next == 1)
                return true;
            else if (next < 256 && hash_has(hash, next))
                return false;
            n = next;
        }
    }
    

  • 0
    L

    I don't think this is a good solution. in the interview, how can you come up a list with these magic numbers quickly and correctly?


  • 0
    L

    I mean, for this problem, you may be able to memorize those numbers, but if a similar problem comes up, how to guarantee that you can generate this list correctly in time is the issue.


  • 0
    W

    Here is my Java code.

        int temp = 0;
        while(n != 1) {
        	if(n == 4 || n == 16 || n == 37 || n == 58 || n == 89 || n == 145 || n == 42 || n == 20)
            	return false;
        	
            while(n / 10 > 0) {
                temp += (n % 10) * (n % 10);
                n = n / 10;
            }
            temp += n * n;
            n = temp;
            temp = 0;
        }
        return true;
    

Log in to reply
 

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