Happy Number

This problem has no linked list in it, and that is why interviewers like it. It checks whether you see that "keep applying a function" builds a chain of states, and that a chain which repeats is a cycle, which is exactly what fast and slow pointers find.

The problem

Take a positive whole number. Replace it with the sum of the squares of its digits, and keep doing that. If the process reaches 1, the number is happy. If it never reaches 1, it must fall into a loop that repeats forever, and the number is not happy. Return whether the input is happy.

• 7 → True. 7 → 49 → 97 → 130 → 10 → 1. For example 97 gives 81 + 49 = 130.
• 2 → False. 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4, and 4 is where we already were. The loop never contains 1.

Constraints: 1 ≤ n ≤ 2³¹ − 1.

Clarifying questions

• Is 1 itself happy? Yes: it is already 1.
• Can the sequence grow forever instead of looping? No, and it is worth proving (see below). This is the question a strong candidate asks.
• Is zero or a negative number possible? No, the input is positive.

Approach 1: remember every value

Keep a set of the numbers you have seen. Step forward until you reach 1 (happy) or a number already in the set (a loop, not happy).

1def digit_square_sum(number: int) -> int:2    """Sum of the squares of the decimal digits of number."""3    total = 04    while number > 0:5        number, digit = divmod(number, 10)6        total += digit * digit7    return total8910def is_happy_with_set(number: int) -> bool:11    """Follow the chain, remembering every value seen."""12    seen: set[int] = set()13    while number != 1 and number not in seen:14        seen.add(number)15        number = digit_square_sum(number)16    return number == 1

Why it ends. A number with d digits maps to at most 81 × d. For any number of four or more digits, that is much smaller than the number itself: 9,999 maps to at most 324, and even 2³¹ − 1, with 10 digits, maps to at most 810. Every number of three digits or fewer maps to at most 9² × 3 = 243. So after a step or two the value stays at or below 243 forever. There are only 243 possible values down there, so within a few hundred steps the chain must repeat one.

Time: O(log n) for the first step (the number of digits), then a bounded number of steps on small values. Space: the set holds every value in the chain; that is small here, but it is still memory that grows with the chain.

This solution is fine for this problem, and many interviewers accept it. The follow-up is "can you do it without the set?".

The key insight

Look at the process as a linked list. Each number is a node. Its next is digit_square_sum(number). Every number has exactly one next number, so starting from n you walk a chain. The chain either reaches 1, or it enters a loop that does not contain 1.

And 1 is itself a loop of length one, because 1² = 1. So the chain always ends in a cycle. The only question is which cycle: the one at 1, or another one. That is cycle detection, and fast and slow pointers do it in O(1) space. Run them until fast reaches 1 or the two meet. If fast is at 1, the number is happy.

Approach 2: fast and slow pointers

1. slow starts at n. fast starts one step ahead, at digit_square_sum(n).
2. While fast is not 1 and the two differ, move slow one step and fast two steps.
3. Return whether fast is 1.

1def is_happy(number: int) -> bool:2    """Floyd's cycle detection on the chain n -> digit_square_sum(n)."""3    slow = number4    fast = digit_square_sum(number)5    while fast != 1 and slow != fast:6        slow = digit_square_sum(slow)7        fast = digit_square_sum(digit_square_sum(fast))8    return fast == 1

Starting fast one step ahead lets the loop test slow != fast right away without a special first round. The gap argument still holds, because the gap still shrinks by one per step.

Dry run on 7 (happy):

Fast reaches 1, so the result is True.

Dry run on 2 (not happy). The loop is 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4, eight numbers long.

They meet at 42 and fast is not 1, so the result is False.

Time: O(log n). The first call costs one operation per digit of n; after that every value is at most 243, so each call costs at most three digit operations and the number of steps is bounded by a constant. Space: O(1).

Because both values are plain integers, the comparison is != on numbers, not is on nodes. Two states are the same state exactly when the numbers are equal.

Edge cases

• n = 1. fast starts at digit_square_sum(1) = 1, the loop never runs, and the answer is True.
• Powers of ten. 10, 100, 1,000 all map straight to 1. The loop exits on the first check.
• Very large n. 2³¹ − 1 = 2,147,483,647 maps to 260 in one step, and from then on everything stays small.

Follow-ups

• "Prove it doesn't grow forever." Use the bound above: a d-digit number maps to at most 81d, which is smaller than the number once d ≥ 4, and three-digit numbers map to at most 243.
• "Return the length of the unhappy loop." After slow and fast meet, hold one still and step the other until it returns, counting steps. For 2 this gives 8.
• "Use a different base or power." The same code works with divmod(number, base) and digit ** power. The cycle argument only needs the state space to be finite.