DSA Happy Numbers

The problem

A happy number is a number whose digit-square sums eventually reach 1. Each step replaces the number with the sum of the squares of its digits.

The answer is True or False. A chain that reaches 1 proves True. A chain that repeats a value proves False, because it will loop forever.

cases = [
    (19, True),
    (7, True),
    (10, True),
    (23, True),
    (2, False),
    (4, False),
]
for n, expected in cases:
    print("number", n, "happy:", expected)

The chain from 19 runs 19, 82, 68, 100, then 1. The chain from 2 reaches 4 and later comes back to 4.

Intuition: follow the chain and watch for a repeat

The first idea follows the chain one step at a time. It stops at 1 with a happy verdict. A repeated value is the warning sign, because the steps after it must repeat too.

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

chain = [19]
while chain[-1] != 1:
    chain.append(digit_square_sum(chain[-1]))
print("chain from 19:", chain)
chain = [2]
while True:
    nxt = digit_square_sum(chain[-1])
    chain.append(nxt)
    if nxt in chain[:-1]:
        break
print("chain from 2:", chain)
print("first repeated value:", chain[-1])

The happy chain has five entries and stops. The unhappy chain returns to 4 after nine steps. Without a repeat check, that second chain never ends.

Brute force: store every visited value in a set

The brute force stores each visited value in a set, a store that answers membership at once. A new value already in the set proves a cycle. The value 1 proves a happy ending.

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

def is_happy_set(n):
    seen = set()
    steps = 0
    while n != 1 and n not in seen:
        seen.add(n)
        n = digit_square_sum(n)
        steps += 1
    return n == 1, steps, len(seen)

for n in [19, 7, 2, 4]:
    happy, steps, stored = is_happy_set(n)
    print("number", n, "happy:", happy, "steps:", steps, "values stored:", stored)

The set method is correct and simple. Its cost is memory. Every visited value stays in the set until the verdict.

The optimal solution: two walkers, slow and fast

Floyd's method keeps two walkers on the chain, a slow walker taking one step and a fast walker taking two steps per round. Meeting walkers prove a cycle, and a fast walker reaching 1 proves a happy ending.

No set is stored at all. The whole state is two numbers. The slow and fast walkers start one and two steps ahead of the input.

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

def is_happy(n):
    slow = digit_square_sum(n)
    fast = digit_square_sum(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

cases = [(19, True), (7, True), (10, True), (23, True), (2, False), (4, False)]
for n, expected in cases:
    result = is_happy(n)
    print("number", n, "->", result, "expected:", expected, "match:", result == expected)

All six cases from the start of the article pass. Two walkers replace the whole visited set. The method first appeared on linked lists in the Beginner course.

Walkthrough: the walkers on 19 and on 2

The walk prints both walkers after each round. The happy input ends with the fast walker on 1. The unhappy input ends with the walkers equal.

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

def trace(n):
    slow = digit_square_sum(n)
    fast = digit_square_sum(digit_square_sum(n))
    print("start", n, "- slow", slow, "fast", fast)
    rounds = 0
    while fast != 1 and slow != fast:
        slow = digit_square_sum(slow)
        fast = digit_square_sum(digit_square_sum(fast))
        rounds += 1
        print("round", rounds, "- slow", slow, "fast", fast)
    print("verdict for", n, ":", fast == 1)

trace(19)
trace(2)

On 19 the fast walker reaches 1 in one round. On 2 the walkers meet at a shared value after a few rounds. Equal walkers can only happen on a loop.

Complexity

Each round does a fixed number of digit-square steps, and the number of rounds matches the chain length before the verdict, so the time is O(k) for a chain of k values. Floyd's method stores two numbers, so its space is O(1), while the set method stores k values, so its space is O(k).

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

def cost(n):
    seen = set()
    current = n
    while current != 1 and current not in seen:
        seen.add(current)
        current = digit_square_sum(current)
    slow = digit_square_sum(n)
    fast = digit_square_sum(digit_square_sum(n))
    rounds = 0
    while fast != 1 and slow != fast:
        slow = digit_square_sum(slow)
        fast = digit_square_sum(digit_square_sum(fast))
        rounds += 1
    return len(seen), rounds

for n in [19, 2, 4, 20]:
    stored, rounds = cost(n)
    print("number", n, "- set stores:", stored, " floyd rounds:", rounds, " floyd values held: 2")

The rounds stay close to the chain length. The saving is memory, not rounds. The set pays one stored value per chain entry, and Floyd pays none.

Edge cases and pitfalls

The number 1 is already happy, with no steps to take. A single digit squares to a small chain at once. Zero is not happy, because its digit-square sum is itself and the walkers start equal, away from 1.

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

def is_happy(n):
    slow = digit_square_sum(n)
    fast = digit_square_sum(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

print("already 1:", is_happy(1))
print("100 reaches 1 in one step:", is_happy(100), digit_square_sum(100))
print("zero:", is_happy(0))
print("single digit happy, 7:", is_happy(7))
print("single digit unhappy, 3:", is_happy(3))
print("large happy, 1000:", is_happy(1000))

The pitfall is stopping too late or never. A check for 1 alone never fires on an unhappy chain. The meeting check is what gives unhappy numbers a verdict.