We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Happy Number

Difficulty: Easy

Problem Description

Write an algorithm to determine if a number n is happy. A happy number is defined by the process of replacing the number by the sum of the squares of its digits, and repeating this process until the number equals 1 or loops endlessly in a cycle that does not include 1. Return true if n is a happy number, and false if not.

Key Insights

  • A happy number eventually reaches 1 when the described process is followed.
  • If a number does not reach 1, it will enter a cycle of numbers.
  • We can use a set to track numbers we've seen to detect cycles.
  • The sum of the squares of the digits can be efficiently calculated.

Space and Time Complexity

Time Complexity: O(log n) for the number of digits in n, multiplied by the number of iterations until we find a cycle or reach 1. Space Complexity: O(log n) for storing the numbers we've seen in a set.

Solution

To determine if a number is happy, we can use a set to store the numbers we have encountered during the process. We repeatedly calculate the sum of the squares of the digits of the current number. If we reach 1, the number is happy; if we encounter a number we have seen before, it means we are in a cycle, and thus the number is not happy.

Code Solutions

def isHappy(n: int) -> bool:
    def get_next(number: int) -> int:
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = get_next(n)

    return n == 1
← Back to All Questions