52. Happy Number

Problem Statement

Write an algorithm to determine if a number n is "happy".

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

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19 Output: true Explanation: 1^2 + 9^2 = 1 + 81 = 82 8^2 + 2^2 = 64 + 4 = 68 6^2 + 8^2 = 36 + 64 = 100 1^2 + 0^2 + 0^2 = 1 + 0 + 0 = 1

Example 2:

Input: n = 2 Output: false

Solution

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

        slow = n
        fast = get_next(n)

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

        return fast == 1

Explanation

This problem can be solved by detecting a cycle in a sequence of numbers. If a number is not happy, it will eventually enter a cycle that does not include 1. If it is happy, it will eventually reach 1.

We can use Floyd's Cycle-Finding Algorithm (the tortoise and hare approach) to detect if the sequence of numbers generated by the sum-of-squares process enters a cycle.

  1. get_next Function: A helper function get_next(num) calculates the sum of the squares of the digits of a given number.

  2. Initialize Pointers:

    • slow pointer starts at n.
    • fast pointer starts at get_next(n).

  3. Cycle Detection:

    • We iterate using a while loop as long as fast is not 1 and slow is not equal to fast.
    • In each step, slow moves one step (slow = get_next(slow)).
    • fast moves two steps (fast = get_next(get_next(fast))).
    • If slow and fast meet (i.e., slow == fast), it means a cycle has been detected.

  4. Determine Happiness:

    • After the loop, if fast is 1, it means the sequence eventually reached 1, so the number is happy. Return True.
    • If fast is not 1 (meaning slow == fast and they met in a cycle that doesn't include 1), the number is not happy. Return False.

Time and Space Complexity:

  • Time Complexity: The sequence of numbers generated by the sum-of-squares process is bounded. For numbers less than 1000, the maximum sum of squares of digits is for 999 (9^2 + 9^2 + 9^2 = 243). For numbers greater than 999, the sum of squares of digits will eventually become less than 243. This means the sequence will eventually enter a cycle or reach 1. Therefore, the time complexity is effectively O(log n) or O(number of digits), as the number of steps is limited by the maximum possible sum of squares.
  • Space Complexity: O(1), as we only use a few extra variables.