algoadvance

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.

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

Clarifying Questions

1. Input Range: Are we constrained to positive integers only?
   • Positive integers only as per the problem definition.
2. Edge Cases: Should we consider any specific edge cases like very large numbers?
   • We should consider the process for any given positive integer, large or small.
3. Output: What kind of output is expected?
   • A boolean value: True if the number is a happy number, False otherwise.

Strategy

To determine if a number is a happy number:

1. Cycle Detection: Use the concept of detecting cycles in a sequence since if a number loops endlessly in a cycle (other than 1), it is not a happy number.

2. Set for History: Utilize a set to keep track of numbers that we have already seen in the process. If we encounter a number that is already in the set, we are in a cycle and can return False.

3. Sum of Squares Function:
   • Write a helper function to compute the sum of squares of the digits of a number.
4. Iteration:
   • Begin with the input number and repeatedly replace it with the sum of the squares of its digits.
   • If the result is 1, return True.
   • If a number repeats (detected by checking the set), return False.

Code

def isHappy(n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum
    
    seen = set()  # To track already seen numbers to detect cycles
    
    while n != 1 and n not in seen:
        seen.add(n)
        n = get_next(n)
        
    return n == 1

# Example usage
print(isHappy(19))  # Output: True, because 19 is a happy number
print(isHappy(2))   # Output: False, because 2 is not a happy number

Time Complexity

• Time Complexity: O(Φ(d)) - where d is the number of digits in n and Φ is the happy number process’s duration until it halts.
  • Typically, the digits and their sum squares will be constrained and manageable since the cycle detection ensures we stop early if a cycle is found.
• Space Complexity: O(Φ(d))
  • The space is mainly used by the set to keep track of numbers we have seen, which is also bounded by the numbers forming the cycle or the path to 1.

This approach ensures efficient detection of happy numbers, taking advantage of cycle detection in sequences.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?