Problem statement

Write an algorithm to decide whether a positive integer n is happy.

A happy number is defined by this process: replace the number by the sum of the squares of its digits, and repeat. If the process reaches 1 the number is happy. If it loops forever without reaching 1, it is not.

Return true if and only if n is happy.

Example 1

Input: n = 19
Output: true
Explanation: 1²+9²=82, 8²+2²=68, 6²+8²=100, 1²+0²+0²=1.

Example 2

Input: n = 2
Output: false
Explanation: The sequence enters the cycle 4, 16, 37, 58, 89, 145, 42, 20, 4, …

Example 3

Input: n = 1
Output: true

Constraints

• 1 <= n <= 200000

Hints for Happy Number

1. Hint 1

   The process either reaches 1 or repeats a value it has already produced — there is no third outcome.

2. Hint 2

   Remember every value you have seen in a hash set; seeing one twice means you are in a cycle.

3. Hint 3

   Because it is a sequence that eventually cycles, Floyd's slow/fast pointer also works and uses O(1) memory.

How to solve Happy Number

The digit-square map sends every number to a small value quickly, so the process must either hit 1 or revisit a number and loop forever. Detect the loop with a set of visited values.

Approach

1. Loop while n != 1 and n has not been seen before.
2. Record n in the seen set.
3. Replace n with the sum of the squares of its digits.
4. Return n == 1 when the loop exits.

Why it works

For any number the sum of squared digits is at most 81 × digits, so a value with d digits maps to something far smaller until it falls below a few hundred, after which the sequence lives in a finite set and must repeat. Once a value repeats the process is periodic and can never reach 1, so revisiting is proof of unhappiness.

Complexity

• Time — O(log n) per step, a bounded number of steps
• Space — O(log n) for the seen set

Pitfalls

• Floyd's tortoise-and-hare works too (the map is a function, so the walk is a ρ-shaped sequence) and drops the set.
• Check n != 1 before inserting, otherwise 1 itself is recorded and the exit condition gets confusing.

Reference solution

Python

def isHappy(n: int) -> bool:
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        total = 0
        while n > 0:
            d = n % 10
            total += d * d
            n //= 10
        n = total
    return n == 1

Java

public static boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    while (n != 1 && !seen.contains(n)) {
        seen.add(n);
        int total = 0;
        int x = n;
        while (x > 0) {
            int d = x % 10;
            total += d * d;
            x /= 10;
        }
        n = total;
    }
    return n == 1;
}

C++

bool isHappy(int n) {
    unordered_set<int> seen;
    while (n != 1 && seen.count(n) == 0) {
        seen.insert(n);
        int total = 0;
        int x = n;
        while (x > 0) {
            int d = x % 10;
            total += d * d;
            x /= 10;
        }
        n = total;
    }
    return n == 1;
}

JavaScript

var isHappy = function(n) {
    const seen = new Set();
    while (n !== 1 && !seen.has(n)) {
        seen.add(n);
        let total = 0;
        while (n > 0) {
            const d = n % 10;
            total += d * d;
            n = Math.floor(n / 10);
        }
        n = total;
    }
    return n === 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Remove Duplicates from an Unsorted Linked List Easy
• Two Sum IV - Input is a BST Easy