{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Happy Number – Solution & Complexity

Interview solutions
/
Happy Number

Solution Walkthrough

  1. Step 1: Understand the Pattern

    • Each step replaces n with the sum of the squares of its digits.
    • Because the values stay bounded, the sequence must eventually repeat.
    • The number is happy only if that sequence reaches 1.

  2. Step 2: Compute the Digit-Square Sum

    • Peel digits off with % 10 and // 10.
    • Square each digit and accumulate the total.
    • This helper drives every step of the process.
    def digit_square_sum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total

  3. Step 3: Detect the Cycle with a Set

    • Keep a seen set of numbers already visited.
    • Stop with False if a value repeats, or True if it reaches 1.
    • This is O(1)-ish space because the reachable values are bounded.
    def is_happy(n):
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = digit_square_sum(n)
    return n == 1

  4. Step 4: Final Solution and Complexity

    • Floyd's slow/fast pointers detect the cycle without a set.
    • Time is O(log n) per step across a bounded number of steps.
    • Space is O(1).
    def is_happy(n: int) -> bool:
    def digit_square_sum(value):
        total = 0
        while value > 0:
            value, digit = divmod(value, 10)
            total += digit * digit
        return total

    slow = n
    fast = digit_square_sum(n)
    while fast != 1 and slow != fast:
        slow = digit_square_sum(slow)
        fast = digit_square_sum(digit_square_sum(fast))
    return fast == 1

FAQ

See also

Practice Happy Number online (run code in the browser)Roman to Integer solution (easy)3Sum solution (medium)Accounts Merge solution (medium)Add Two Numbers solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?