Happy Number

Q: What is the time complexity of Happy Number?

O(log n) . The first step reads the O(log n) digits of n ; every later value is below 1000, where no walk visits more than 20 numbers before it reaches 1 or repeats. The hash set holds those numbers, and Floyd's version uses O(1) space.

EasyFast and slow pointers Hashing

+10

Start from a positive integer n and replace it with the sum of the squares of its digits, over and over. For example, 12 becomes 1² + 2² = 5. If this process reaches 1, n is a happy number; otherwise it circles forever through numbers that never include 1. Return true if n is happy and false if it is not.

Function

isHappy(n: integer) → boolean

ninteger: the positive integer to test
Returnsboolean: true if repeating the digit-square sum reaches 1, false if it loops forever

Constraints

1 ≤ n ≤ 2³¹-1

Examples

Input: n = 7
Output: true
Explanation: 7 becomes 49, then 4² + 9² = 97, then 130, then 10, then 1. The process reaches 1, so 7 is happy.

Input: n = 2
Output: false
Explanation: 2 becomes 4, 16, 37, 58, 89, 145, 42, 20 and then 4 again. From there the same eight numbers repeat forever and never reach 1.

Input: n = 100
Output: true
Explanation: 1² + 0² + 0² = 1, so 100 reaches 1 after one step.

Follow-up

How would you count the happy numbers from 1 to 10^6 quickly, reusing the answers for numbers below 1000 instead of walking every start from scratch?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The walk cannot grow without bound: a 10-digit number maps to at most 10 × 81 = 810, and a number below 1000 to at most 243. So it stays among fewer than 1000 values and must reach 1 or repeat. That makes this cycle detection: remember what you have seen, or run a slow and a fast walker.

Remember every number you have seen

Intuition

Keep every number you visit in a hash set and stop at 1 or at a repeat. The next number depends only on the current one, so once a number comes back, everything after it repeats and 1 can never appear. For 2 the set fills with 2, 4, 16, 37, 58, 89, 145, 42 and 20, and the next value, 4, is already there.

After the first step every value is below 1000, so a flag array of 1000 entries can replace the set.

Algorithm

Create an empty hash set seen.
While n is not 1, return false if n is in seen.
Otherwise add n to seen and replace n with the sum of the squares of its digits.
When the loop ends, n is 1: return true.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    seen = set()
    while n != 1:
        if n in seen:
            return False  # back at an earlier number: a loop without 1
        seen.add(n)
        n = digitSquareSum(n)
    return True

Fast and slow walkers (Floyd's cycle detection)

Intuition

Each number has one arrow, to its digit-square sum, so the walk from n either reaches 1 or runs into a loop. Floyd's method finds the loop with no storage: slow takes one step per round and fast takes two.

If the loop avoids 1, both walkers end up circling it, and each round fast gains one step, so they land on the same number: for 2 they meet at 42 after seven rounds. If the walk reaches 1, fast gets there first and stays, since 1 maps to 1. For 7, fast moves 49, 130, 1 while slow is still on 97. The rounds are a small multiple of the walk's length, and the memory is two integers.

Algorithm

Write a helper that returns the sum of the squares of a number's digits.
Set slow = n and set fast to the number one step after n.
While fast is not 1 and slow differs from fast, move slow one step and fast two steps.
Return whether fast is 1.

def digitSquareSum(n):
    total = 0
    while n > 0:
        digit = n % 10
        total += digit * digit
        n //= 10
    return total


def isHappy(n):
    slow = n
    fast = digitSquareSum(n)
    # fast moves two steps for every step of slow; they meet only inside a loop.
    while fast != 1 and slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    return fast == 1

Pitfalls and edge cases

Looping until the value is 1 with no other exit. For 2 that loop never ends.
Starting both walkers on the same number and testing slow != fast before the first move. The loop never runs, and 7 comes out unhappy.
Returning slow == 1. For 7, fast reaches 1 and the loop stops while slow is on 97.
Declaring n unhappy whenever the walkers meet. They also meet on 1, so check where.
Summing the digits, or squaring the whole number. For 12 the next value is 1² + 2² = 5, not 3 and not 144.

Frequently asked questions3

What is the time complexity of Happy Number?

O(log n). The first step reads the O(log n) digits of n; every later value is below 1000, where no walk visits more than 20 numbers before it reaches 1 or repeats. The hash set holds those numbers, and Floyd's version uses O(1) space.

Why do all unhappy numbers end up at 4?

Checking every number below 1000 shows one loop that avoids 1: 4, 16, 37, 58, 89, 145, 42, 20 and back to 4. Every start drops below 1000 after one step, so every unhappy number falls into it. Stopping at 4 works, but you would have to justify that fact in an interview.

How is Happy Number related to Linked List Cycle?

Both ask whether following one arrow from each item returns to an item already visited. Here the arrow is the digit-square sum; in a linked list it is the next pointer. That is why fast and slow walkers solve both in constant memory.