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

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

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

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

• 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?

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

• 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;
``````

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