Happy Number 🧠

LeetCode Link: Happy Number

Difficulty: Easy

Problem Explanation 📝

Problem: LeetCode 202 - Happy Number

Description: A happy number is a number defined by the following process:

• Starting with any positive integer, replace the number by the sum of the squares of its digits.
• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
• Those numbers for which this process ends in 1 are happy.

Intuition: To determine if a number is a happy number, we can use a set to keep track of all the numbers we have encountered during the process. If we encounter a number that we have seen before, it means there is a cycle, and the number is not a happy number.

Approach:

1. We start with the given number and calculate the sum of the squares of its digits.
2. We continue this process until the sum becomes 1 or until we encounter a number that we have seen before.
3. If the sum becomes 1, we return true, indicating that the number is a happy number.
4. If we encounter a number we have seen before, we return false, indicating that the number is not a happy number.

⌛ Time Complexity: The time complexity of this approach is difficult to determine as it depends on the number of iterations required to reach 1 or find a cycle. In practice, the process usually converges quickly for happy numbers, so the time complexity is considered to be approximately O(log n).

💾 Space Complexity: The space complexity is O(log n) as we use a set to keep track of the numbers encountered during the process, and the number of unique numbers encountered is limited.

Solutions 💡

Cpp 💻

class Solution {
  public:
    bool isHappy(int n) {
        unordered_set<int> seen;

        while (n != 1 && seen.find(n) == seen.end()) {
            seen.insert(n);
            n = getNextNumber(n);
        }

        return n == 1;
    }

  private:
    int getNextNumber(int n) {
        int sum = 0;

        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }

        return sum;
    }
};

Python 🐍

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(num):
            next_num = 0
            while num > 0:
                num, digit = divmod(num, 10)
                next_num += digit**2
            return next_num

        slow, fast = n, get_next(n)

        while fast != 1 and slow != fast:
            slow = get_next(slow)
            fast = get_next(get_next(fast))

        return fast == 1