202. Happy Number - cocoder39/coco39_LC GitHub Wiki

202. Happy Number

algorithm is easy, but you need understand why the algorithm works!

given a positive integer n, then 0 <= n <= INT_MAX = 2 ^ 31 - 1

2 ^ 31 - 1 < 2 ^ 31 = (2 ^ 10) ^ 3 * 2 = 1024 ^ 3 * 2 ~= 1000 ^ 3 * 2 < 9,999,999,999. Thus helper(INT_MAX) < helper(9,999,999,999) = 9 ^ 2 * 10 = 810. all results must be within [1, 810], then there must exist a loop and at most take O(810) = O(1) time to find the loop

  • (1) use set to detect the loop, space complexity is O(810) = O(1)
  • (2) fast and slow pointers to detect loop
class Solution {
public:
    bool isHappy(int n) {
        if (n <= 0) {
            return false;
        } 
        
        unordered_set<int> st;
        while (n != 1 && st.find(n) == st.end()) {
            st.insert(n);
            n = helper(n);
        }
        return n == 1;
    }
private:
    int helper(int n) {
        int res = 0;
        while (n > 0) {
            int k = n % 10;
            res += k * k;
            n /= 10;
        }
        return res;
    }
};

class Solution {
public:
    bool isHappy(int n) {
        if (n <= 0) {
            return false;
        } 
        
        int fast = n, slow = n;
        do {
            slow = helper(slow);
            fast = helper(helper(fast));
        } while (slow != 1 && slow != fast);
        
        return slow == 1;
    }
private:
    int helper(int n) {
        int res = 0;
        while (n > 0) {
            int k = n % 10;
            res += k * k;
            n /= 10;
        }
        return res;
    }
};
⚠️ **GitHub.com Fallback** ⚠️