Happy Number

Medium·Tagsmathtwo-pointershash-table

Problem Statement

Write an algorithm to determine if a number `n` is a happy number. A happy number is a number defined by the following process: 1. Starting with any positive integer, replace the number by the sum of the squares of its digits. 2. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. 3. Those numbers for which this process ends in 1 are happy.

Examples

Example 1

Input

n: 19

Sequence

Output

"true"

Why

1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1

Example 2

Input

n: 2

Sequence

Output

"false"

Why

The process will get caught in an infinite cycle (4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4) and never reach 1.

Constraints

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

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

How does this relate to Linked Lists? Treat the initial number as the 'head', and the sum of its squared digits as the 'next' node.

Hint 2

If it's a happy number, the sequence will eventually reach 1, and 1 always points to 1 (a self-loop).

Hint 3

If it's not a happy number, the sequence will get caught in a repeating cycle.

Hint 4

You can use the Fast and Slow pointers technique here! Move the slow pointer by applying the digit square sum operation once, and move the fast pointer by applying it twice.