{x}
blog image

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

Solution Explanation:

The problem asks to determine if a number is a "happy number." A happy number is a number where repeatedly summing the squares of its digits eventually results in 1. If the process enters a cycle without reaching 1, it's not a happy number.

Two approaches are presented to solve this:

Approach 1: Using a Set to Detect Cycles

This approach leverages a Set (or HashSet in other languages) to efficiently detect cycles. The algorithm works as follows:

  1. Initialization: A set vis is created to store the numbers encountered during the process.
  2. Iteration: The algorithm iterates while the current number n is not 1 and hasn't been seen before (not in vis).
  3. Digit Squaring: In each iteration, the sum of squares of the digits of n is calculated and assigned to x.
  4. Cycle Detection: Before updating n to x, n is added to vis. If n is already in vis, it means a cycle has been detected, and the algorithm terminates.
  5. Termination: The algorithm terminates when either n becomes 1 (happy number) or a cycle is detected (not a happy number).

Time Complexity: O(log n). The number of iterations is logarithmic because the number of digits decreases with each iteration. The set operations (insertion and lookup) are generally O(1) on average.

Space Complexity: O(log n) in the worst case because the set vis could store up to a logarithmic number of unique numbers.

Approach 2: Floyd's Tortoise and Hare Algorithm (Cycle Detection)

This approach employs Floyd's cycle-finding algorithm, also known as the "tortoise and hare" algorithm. It's more efficient in space complexity compared to Approach 1.

  1. Initialization: Two pointers, slow and fast, are initialized to n and next(n) respectively, where next(n) calculates the next number in the sequence.
  2. Iteration: The algorithm iterates until slow and fast meet. slow moves one step at a time, while fast moves two steps at a time (next(next(fast))).
  3. Cycle Detection: If slow and fast meet, it indicates a cycle. The meeting point determines whether the cycle contains 1 or not.
  4. Termination: If slow (and hence fast) equals 1 at the meeting point, it's a happy number; otherwise, it's not.

Time Complexity: O(log n). The number of iterations is still logarithmic, similar to Approach 1.

Space Complexity: O(1). This approach uses only a constant amount of extra space to store the slow and fast pointers.

Code Examples in Different Languages:

The code examples for both approaches are provided in the problem description. The Python3 and Java examples are particularly clear. Note that the C code uses a more concise approach for getNext function. The other languages follow similar logic with minor syntax differences. Approach 2 (Floyd's algorithm) is generally preferred due to its better space complexity.