Leetcode - 202. Happy Number

문제

주어진 수의 각 자리수를 제곱해서 모두 더하고, 그 값을 또 계속 반복할때, 1이 나오면 true. 아니면 false 리턴하기.

Input: n = 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 02 = 1

https://leetcode.com/problems/happy-number/

해결

1을 찾는건 쉬운데 오히려, 1이 안나올때 어떻게 반복문을 종료할것인지 찾는데 생각을 해야했던 문제.
답이 false인 값으로 손으로 값을 나열해봤더니, 반드시 내부 loop가 생성된다. 따라서 내부 loop가 생성되면 무조건 false 케이스이다. 만약 happy넘버였다면 그 loop내에서 분명히 1이 나왔어야하기 때문.

해시테이블을 이용해 해당 값이 이전에 등장했는지 안했는지 저장했다. collision 해결을 위해 링크드리스트리반의 해시테이블을 구현. 그리고 squre[10]는 미리 계산해둠.

1. Constraints
 - how do I know end of loop, if awnser is false case
 - 
2. Ideas
 - #1 table: pre calcualte 10 digit. and save it to a table[]
 - #2 table: save the number was happend.
   if already exist -> this is a cycle -> the answer is false.
3. Test Cases
 - 2 -> false
 - 1 -> true
 - maximun input INT_MAX (limits.h)

#define HSIZE 40093

struct elem {
    int val;
    struct elem *next;
};
struct elem *table[HSIZE];

struct elem *hash_search(int val)
{
    int hval = val % HSIZE;
    struct elem *node = table[hval];  
    for (; node != NULL; node = node->next) {
        if (node->val == val)
            return node;
    }
    return node;
}

struct elem *hash_add(int val)
{
    /*
    if (hash_search(val) == NULL)
        return NULL;
        */
    int hval = val % HSIZE;
    struct elem *node = (struct elem *)malloc(sizeof(struct elem));
    node->val = val;
    node->next = table[hval];
    table[hval] = node;
    return node;
}

bool isHappy(int n) {
    int squre[10] = {0};
    int tmp = 0;
    memset(table, NULL, sizeof(struct elem *) * HSIZE);
    
    for (int i = 0; i < 10; i++)
       squre[i] = i * i; 
    hash_add(n);
    while (1) {
        tmp += squre[n % 10];
        n = n / 10;
        if (n == 0) { /* next round */
            if (tmp == 1)
                return true;
            if (hash_search(tmp)) /* cycle found */
                break;
            hash_add(tmp);
            n = tmp;
            tmp = 0;
        }
    }
    return false;
}