# Happy Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/happy-number)
Canonical: https://scaleengineer.com/dsa/problems/happy-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Hash Table
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Airbnb](https://scaleengineer.com/companies/airbnb), [Cisco](https://scaleengineer.com/companies/cisco), [Cognizant](https://scaleengineer.com/companies/cognizant), [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [PayPal](https://scaleengineer.com/companies/paypal), [Snowflake](https://scaleengineer.com/companies/snowflake), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Nike](https://scaleengineer.com/companies/nike), [Swiggy](https://scaleengineer.com/companies/swiggy), [BlackRock](https://scaleengineer.com/companies/blackrock), [X](https://scaleengineer.com/companies/x), [Verily](https://scaleengineer.com/companies/verily), [Jump Trading](https://scaleengineer.com/companies/jump-trading), [FactSet](https://scaleengineer.com/companies/factset)
---
## Problem
Write an algorithm to determine if a number `n` is happy.

A **happy number** is a number defined by the following process:

* Starting with any positive integer, replace the number by the sum of the squares of its digits.
* Repeat the process until the number equals 1 (where it will stay), or it **loops endlessly in a cycle** which does not include 1.
* Those numbers for which this process **ends in 1** are happy.

Return `true` _if_ `n` _is a happy number, and_ `false` _if not_.

**Example 1:**

**Input:** n = 19
**Output:** true
**Explanation:**
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

**Example 2:**

**Input:** n = 2
**Output:** false

**Constraints:**

* `1 <= n <= 231 - 1`

# Approaches
## Brute Force with HashSet
Use a HashSet to track all numbers we've seen during the process. If we encounter a number we've already seen, we've detected a cycle and the number is not happy. If we reach 1, the number is happy.
**Time:** O(log n) - The number of digits in n is O(log n), and we process each digit. The number of iterations before finding a cycle or reaching 1 is bounded. · **Space:** O(log n) - In the worst case, we might store O(log n) numbers in the HashSet before detecting a cycle.
**Pros:** Simple and intuitive implementation; Easy to understand and debug; Guaranteed to terminate
**Cons:** Uses extra space to store all visited numbers; Not the most space-efficient solution
### Explanation
The approach works by repeatedly calculating the sum of squares of digits and storing each intermediate result in a HashSet. When we encounter a number that's already in our set, we know we're in a cycle and can return false. If we reach 1, we return true.

```java
public boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    
    while (n != 1 && !seen.contains(n)) {
        seen.add(n);
        n = getNext(n);
    }
    
    return n == 1;
}

private int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}
```

The `getNext` function extracts each digit by using modulo 10 operation, squares it, and adds to the sum. We then divide by 10 to move to the next digit.
### Algorithm
1. Initialize an empty HashSet to store seen numbers
2. While the current number is not 1 and not in the HashSet:
   - Add the current number to the HashSet
   - Calculate the sum of squares of its digits
   - Update the current number with this sum
3. If the current number is 1, return true
4. Otherwise, return false (cycle detected)

## Floyd's Cycle Detection (Two Pointers)
Use Floyd's cycle detection algorithm with slow and fast pointers. The slow pointer moves one step at a time, while the fast pointer moves two steps. If there's a cycle, they will eventually meet. If the fast pointer reaches 1, the number is happy.
**Time:** O(log n) - Similar to the HashSet approach, we process digits and the number of iterations is bounded. · **Space:** O(1) - We only use two integer variables regardless of input size.
**Pros:** Constant space complexity; No need to store visited numbers; Elegant solution using well-known algorithm
**Cons:** Slightly less intuitive than the HashSet approach; Requires understanding of Floyd's cycle detection algorithm
### Explanation
This approach treats the problem as cycle detection in a sequence. We use two pointers moving at different speeds - if there's a cycle, they will eventually meet at the same number. If the fast pointer reaches 1, we know the number is happy.

```java
public boolean isHappy(int n) {
    int slow = n;
    int fast = n;
    
    do {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    } while (slow != fast);
    
    return slow == 1;
}

private int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}
```

The algorithm works because:
- If there's a cycle, the fast pointer will eventually catch up to the slow pointer
- If the sequence reaches 1, it will stay at 1 (since 1² = 1)
- When the pointers meet, we check if they met at 1
### Algorithm
1. Initialize two pointers (slow and fast) to the input number
2. Repeat until the pointers meet:
   - Move slow pointer one step (calculate sum of squares once)
   - Move fast pointer two steps (calculate sum of squares twice)
3. When pointers meet, check if they met at 1
4. Return true if they met at 1, false otherwise

# Solutions
### Java

```java
class Solution { public boolean isHappy ( int n ) { int slow = n , fast = next ( n ); while ( slow != fast ) { slow = next ( slow ); fast = next ( next ( fast )); } return slow == 1 ; } private int next ( int x ) { int y = 0 ; for (; x > 0 ; x /= 10 ) { y += ( x % 10 ) * ( x % 10 ); } return y ; } }
```

### CPP

```cpp
class Solution { public: bool isHappy ( int n ) { auto next = []( int x ) { int y = 0 ; for (; x ; x /= 10 ) { y += pow ( x % 10 , 2 ); } return y ; }; int slow = n , fast = next ( n ); while ( slow != fast ) { slow = next ( slow ); fast = next ( next ( fast )); } return slow == 1 ; } };
```

### Python

```python
class Solution : def isHappy ( self , n : int ) -> bool : def next ( x ): y = 0 while x : x , v = divmod ( x , 10 ) y += v * v return y slow , fast = n , next ( n ) while slow != fast : slow , fast = next ( slow ), next ( next ( fast )) return slow == 1
```