Decide Whether Repeatedly Summing Squared Digits Reaches 1
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Starting from a positive integer, repeatedly replace the number by the sum of the squares of its decimal digits. Return whether this process eventually reaches 1.
### Function Signature
```python
def is_happy(n: int) -> bool:
```
### Rules
- One step replaces the current number by the sum of the squares of its digits; for example, 82 becomes `8 * 8 + 2 * 2 = 68`.
- Return `True` if the number becomes 1 after zero or more steps, so `n = 1` itself returns `True`.
- Otherwise the numbers eventually repeat in a cycle that never contains 1; return `False`.
### Constraints
- `1 <= n <= 2^31 - 1`
### Examples
**Example 1**
```text
Input: n = 7
Output: True
```
7 → 49 → 97 → 130 → 10 → 1.
**Example 2**
```text
Input: n = 2
Output: False
```
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4, and the cycle starting at 4 repeats forever without reaching 1.
**Example 3**
```text
Input: n = 1
Output: True
```
The number is already 1, so no step is needed.
Overview: Starting from a positive integer, repeatedly replace it by the sum of the squares of its digits and decide whether the sequence reaches 1 or falls into a cycle. It tests cycle detection on an implicit sequence and reasoning about why the values stay bounded.
Start from a positive integer `n`. One step replaces the current number by the sum of the squares of its decimal digits; for example, `82` becomes `8 * 8 + 2 * 2 = 68`.
Implement `is_happy(n)`. Return `True` if the number becomes `1` after zero or more steps, so `n = 1` itself returns `True`. Otherwise the numbers eventually repeat in a cycle that never contains `1`; in that case return `False`. In JavaScript, Java and C++ return the language's boolean (`true` / `false`).
### Constraints
- `1 <= n <= 2^31 - 1` (2147483647)
- `n` fits in a signed 32-bit integer (Java `int`, C++ `int`); no value produced by the process exceeds `2^31 - 1`.
### Example 1
```text
Input: n = 7
Output: True
```
7 -> 49 -> 97 -> 130 -> 10 -> 1.
### Example 2
```text
Input: n = 2
Output: False
```
2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4, and the cycle starting at 4 repeats forever without reaching 1.
Constraints
- 1 <= n <= 2^31 - 1 (2147483647)
- n fits in a signed 32-bit integer (Java int, C++ int); no value produced by the process exceeds 2^31 - 1
Examples
Input: (7,)
Expected Output: True
Explanation: Source Example 1: 7 -> 49 -> 97 -> 130 -> 10 -> 1.
Input: (2,)
Expected Output: False
Explanation: Source Example 2: 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 repeats without reaching 1.
Hints
- Write a helper that performs one step: take each decimal digit of the current number and add up the squares.
- The statement says a number that never reaches 1 eventually repeats; think about how you would notice that the sequence has come back to a value it already produced.
- After a single step even the largest allowed n becomes a small number, so the sequence only ever visits a small range of values.