Happy Number

Easy· cycle detection· digits

Problem

Repeatedly replace a positive integer with the sum of the squares of its digits. The number is happy if this process eventually reaches 1; otherwise it loops forever in a cycle. Decide whether a given number is happy.

Examples

Input: n = 19

Output: true

19 → 82 → 68 → 100 → 1.

Input: n = 2

Output: false

Constraints

• 1 <= n <= 2^31 - 1

Hints & approach

Hint 1

The digit-square sum of any large number is much smaller, so values stay bounded.

Hint 2

A bounded sequence that never hits 1 must repeat.

Hint 3

Detect the cycle with a seen-set or with fast and slow pointers.

Approachtry the hints first

Treat the digit-square function as a "next" pointer in an implicit linked list. Values quickly drop below a few hundred, so the sequence either reaches 1 or enters a cycle. Run Floyd's cycle detection: advance slow by one step and fast by two until they meet or fast reaches 1. The number is happy exactly when 1 is reached.

Time O(log n) · Space O(1)

← PreviousPlus One Next →Pow(x, n)