Leetcode : Happy Number

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

Introduction

In the world of mathematics, a “happy number” is defined by a specific 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 considered happy.

Why This Approach?

We use the Floyd’s Tortoise and Hare cycle detection algorithm to determine if a number is happy. This approach is efficient in both time and space. Compared to other methods, like keeping track of all seen numbers, Floyd’s cycle detection is more space-efficient since it uses a constant amount of extra space.

Steps of the Approach

Initial Check:

If the number is less than 2, return whether it is 1 (since 1 is a happy number).

Helper Function:

Create a helper function get_next(n) to compute the sum of the squares of the digits of n.

Cycle Detection:

• Initialize two pointers: slow and fast.
• Use the get_next function to update the pointers.
• If fast reaches 1, return true.
• If slow equals fast, there's a cycle, and return false.

Visual Representation of the Steps

--------------------------------------------------------------
Initial String: "hello"  
Initial List: ['h', 'e', 'l', 'l', 'o']  
Vowels Set: {'A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u'}

--------------------------------------------------------------

-------------------------------------------------------------------------------------------------------------------------------------------------
| **Step** | **Pointers**                  | **Number** | **Digits Squared**  | **Sum of Squares** | **Next Number**   | **Cycle Detection**     |
|----------|-------------------------------|------------|---------------------|--------------------|-------------------|-------------------------|
| **Start**| n = 19                        | 19         | 1² + 9²             | 1 + 81             | 82                | -                       |
| **1**    | slow = 82, fast = 82 (next)   | 82         | 8² + 2²             | 64 + 4             | 68                | -                       |
| **2**    | slow = 68, fast = 68 (next)   | 68         | 6² + 8²             | 36 + 64            | 100               | -                       |
| **3**    | slow = 100, fast = 100 (next) | 100        | 1² + 0² + 0²        | 1                  | 1                 | fast reaches 1 (true)   |
--------------------------------------------------------------------------------------------------------------------------------------------------

-----------------------------------------
Final List: ['h', 'o', 'l', 'l', 'e']  
Final String: "holle"
-----------------------------------------

Final Code:

Note : I have another approach for this problem. Let me know in the comments section if you would like me to add it.

Time Complexity and Space Complexity

Time Complexity : The time complexity is O(log n) because the number of digits reduces each time we compute the sum of squares.

Space Complexity : The space complexity is O(1) since we are using a constant amount of extra space for the two pointers and the helper function.

Quote : “Happiness, whether in numbers or in life, often comes from breaking cycles and finding that one true path to success”