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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Happy Number

Number: 202

Difficulty: Easy

Paid? No

Companies: Google, BlackRock, Amazon, Meta, Snowflake, Microsoft, Swiggy, Accenture, Bloomberg, Apple, J.P. Morgan, tcs, Cognizant, Adobe, Uber, Yahoo, Cisco, Zoho, TikTok, Airbnb, X

Problem Description

Given a positive integer n, determine if it is a happy number. A happy number is defined by repeatedly replacing the number with the sum of the squares of its digits until the number equals 1 (happy) or it loops endlessly in a cycle that does not include 1 (unhappy).

Key Insights

  • The process involves repeatedly computing the sum of squares of digits.
  • If the process reaches 1, the number is happy.
  • If the computed values start repeating (cycle detection), the number is not happy.
  • The cycle can be detected using a hash set to record previously seen numbers or using a two pointers (Floyd’s cycle detection) approach.

Space and Time Complexity

Time Complexity: O(1) – Although the process appears iterative, the sum of squares quickly reduces any number to a bounded range. Space Complexity: O(1) – The number of unique sums computed is bounded, resulting in constant space usage.

Solution

The solution involves computing the sum of the squares of a number's digits in each iteration. We use a hash set to track numbers that have already been seen. If a number repeats, it means we are in a cycle and the number is not happy. If the number becomes 1, it is a happy number. Data structures used include a hash set for cycle detection, and the algorithm uses iterative computation.

Code Solutions

# Function to compute the sum of squares of digits
def sum_of_squares(num):
    total = 0
    while num:
        digit = num % 10      # Extract the last digit
        total += digit * digit  # Add its square to the total
        num //= 10            # Remove the last digit
    return total

def isHappy(n):
    seen = set()              # Initialize a set to keep track of seen numbers
    # Iterate until n becomes 1 or we detect a cycle
    while n != 1 and n not in seen:
        seen.add(n)           # Add current n to the set
        n = sum_of_squares(n) # Compute new n as the sum of squares of digits
    return n == 1             # Return True if n is 1, else False

# Example usage:
print(isHappy(19))  # Expected output: True
print(isHappy(2))   # Expected output: False
← Back to All Questions