Happy Number

Repeatedly replace n by the sum of the squares of its digits. n is happy if this process reaches 1; otherwise it loops forever in a cycle that doesn’t contain 1. Return whether n is happy.

Examples

Input:  n = 19
Output: true     (1² + 9² = 82 → 68 → 100 → 1)

Input:  n = 2
Output: false

Constraints

• 1 ≤ n ≤ 2³¹ − 1

Explanation

It always ends in a cycle

The digit-square sum of any number with d digits is at most 81·d, so values quickly drop below a few hundred and stay there. A sequence stuck in a finite range must eventually repeat. The question is only whether it repeats at 1 (1 → 1) or somewhere else.

Detect the repeat

• With a set: stop when you see a number twice.
• With Floyd’s fast and slow pointers (like Linked List Cycle): advance slow one step and fast two steps until they meet; the number is happy if they meet at 1. This uses O(1) memory.

Complexity

• Time: O(log n) per step, and the number of steps is small. Space: O(1).