Happy Number

Q: Why does the process always reach 1 or a loop?

A number with d digits maps to at most 81 × d , so big numbers shrink fast: any start up to 2^31-1 drops below 1000 after one step, and a number below 1000 maps to at most 243. The walk is trapped among fewer than 1000 values, so it must revisit one, and from then on it cycles. 1 is the only number that maps to itself.

Q: What is the time complexity of Happy Number?

The first step reads the O(log n) digits of n . Every later value is below 1000, and the walk repeats within at most 20 numbers, so the total time is O(log n) . The hash set version stores the visited numbers; 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.

+16 hidden tests on Submit

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 can never run off to infinity. A number with 10 digits maps to at most 10 × 81 = 810, and a number below 1000 maps to at most 3 × 81 = 243, so after one step the walk stays among fewer than 1000 values and must reach 1 or repeat a number. That turns the problem into cycle detection: remember what you have seen, or run a slow and a fast walker and see whether they meet.

Remember every number you have seen

Intuition

Walk the sequence and keep every number in a hash set. Before you move on from a number, check whether it is already in the set. For 2 the set fills with 2, 4, 16, 37, 58, 89, 145, 42 and 20, and the next value is 4, which is already there: the walk has closed a loop without meeting 1, so 2 is not happy. Reaching 1 ends the walk with true.

This is correct because the next number depends only on the current one. Once a number comes back, everything after it repeats exactly, so no new number can appear, and 1 never will.

The walk is short. The first step reads the O(log n) digits of n, and every later value is below 1000, where no walk visits more than 20 different numbers before it reaches 1 or repeats. The set holds those numbers. The C code uses a flag array of 1000 entries as the set and starts recording after the first step, when every value is below 1000.

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

Think of each number as a node with one arrow, pointing to its digit-square sum. Following the arrows from n either reaches 1, whose arrow points back to 1, or runs into a loop. That is the shape of a linked list that may contain a cycle, and Floyd's algorithm detects a cycle without storing anything: slow takes one step per round and fast takes two.

If the loop does not contain 1, both walkers end up circling it, and every round fast gains one step on slow, so the gap shrinks by one until they stand on the same number. For 2 they meet at 42 after seven rounds. If the walk reaches 1, fast gets there first and stays, because the sum for 1 is 1. So stop when fast is 1 or the walkers meet, and answer whether fast is 1.

For 7, slow moves 7, 49, 97 while fast moves 49, 130, 1, and the loop stops with fast on 1. The number of rounds is at most a small multiple of the walk's length, so the time matches the set version, 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

The digit arithmetic is short. Most mistakes are in when the loop stops.

Looping until the value is 1 with no other exit. For 2 that loop never ends.
Starting slow and fast on the same number and testing slow != fast before the first move. The loop never runs, and 7 comes out unhappy. Start fast one step ahead, or move both before the first comparison.
Returning slow == 1 in the Floyd version. fast reaches 1 first and the loop stops right away, while slow can still be on 97.
Summing the digits instead of their squares, or squaring the whole number. For 12 the next value is 1² + 2² = 5, not 3 and not 144.
Declaring n unhappy whenever the walkers meet. 1 maps to itself, so the walkers also meet on 1; check where they met, or stop as soon as fast is 1.

Frequently asked questions4

Why does the process always reach 1 or a loop?

A number with d digits maps to at most 81 × d, so big numbers shrink fast: any start up to 2^31-1 drops below 1000 after one step, and a number below 1000 maps to at most 243. The walk is trapped among fewer than 1000 values, so it must revisit one, and from then on it cycles. 1 is the only number that maps to itself.

What is the time complexity of Happy Number?

The first step reads the O(log n) digits of n. Every later value is below 1000, and the walk repeats within at most 20 numbers, so the total time is O(log n). The hash set version stores the visited numbers; Floyd's version uses O(1) space.

Why do all unhappy numbers end up at 4?

Checking every number below 1000 shows exactly one loop that avoids 1: 4, 16, 37, 58, 89, 145, 42, 20 and back to 4. Since every start drops below 1000, every unhappy number falls into it. A solution can stop as soon as it meets 4, but that relies on a fact you would have to justify in an interview; the set and Floyd's method need no such knowledge.

How is Happy Number related to Linked List Cycle?

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