LeetCode 202 - Happy Number

This problem asks us to determine whether a given positive integer n is a happy number. A happy number is defined through a repeated transformation process. Starting with the original number, we repeatedly replace it with the sum of the squares of its digits.

leetcodeeasyhash-tablemathtwo-pointers

LeetCode Problem 202

Difficulty: 🟢 Easy
Topics: Hash Table, Math, Two Pointers

Solution

Problem Understanding

This problem asks us to determine whether a given positive integer n is a happy number.

A happy number is defined through a repeated transformation process. Starting with the original number, we repeatedly replace it with the sum of the squares of its digits. Eventually, one of two things happens:

  1. The number becomes 1, in which case the process stops and the number is considered happy.
  2. The sequence enters a repeating cycle that never reaches 1, meaning the number is not happy.

For example, if n = 19:

  • 1² + 9² = 82
  • 8² + 2² = 68
  • 6² + 8² = 100
  • 1² + 0² + 0² = 1

Since the process reaches 1, 19 is a happy number.

The input is a single integer n, where:

  • 1 <= n <= 2³¹ - 1

The output should be a boolean:

  • true if n is happy
  • false otherwise

The constraints tell us that n can be fairly large, but still fits inside a standard 32-bit signed integer. However, an important observation is that repeatedly summing digit squares causes numbers to shrink quickly. Even very large numbers eventually become relatively small values.

The main challenge is handling cycles. A naive implementation might keep transforming the number forever if it never reaches 1. For example, 2 enters a repeating loop:

2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

Since 4 appears again, the sequence will repeat forever.

Important edge cases include:

  • n = 1, which is already a happy number.
  • Numbers that quickly fall into a cycle, such as 2.
  • Very large valid inputs near 2³¹ - 1, which must still terminate efficiently.

Approaches

Brute Force Approach

A brute force solution repeatedly computes the sum of squared digits and continues indefinitely until either:

  • The number becomes 1, or
  • We somehow determine that we are stuck in a cycle.

The issue is that without tracking previous states, there is no reliable way to detect infinite repetition. A naive implementation could loop forever on unhappy numbers.

To make brute force workable, we can maintain a list or set of previously seen values. Each time we compute a new number, we check whether it has appeared before. If it has, we know we are in a cycle and can safely return false.

This approach is correct because the sequence is deterministic. A number always maps to exactly one next number. Therefore, revisiting a previous value guarantees repetition.

Key Insight for an Optimal Solution

The key observation is that this problem is fundamentally a cycle detection problem.

Rather than storing all previously visited numbers, we can use Floyd's Cycle Detection Algorithm, also called the Tortoise and Hare approach.

The idea is:

  • A slow pointer moves one transformation at a time.
  • A fast pointer moves two transformations at a time.

If the sequence enters a cycle, the two pointers must eventually meet inside that cycle. If the sequence reaches 1, then the number is happy.

This approach avoids extra memory while still reliably detecting loops.

Approach Time Complexity Space Complexity Notes
Brute Force O(log n) O(log n) Uses a hash set to detect repeated values
Optimal O(log n) O(1) Uses Floyd's cycle detection without extra storage

Although the sequence can iterate several times, the values quickly collapse into a small bounded range, making the practical runtime very small.

Algorithm Walkthrough

We will use Floyd's Cycle Detection Algorithm.

  1. Create a helper function that computes the sum of the squares of the digits of a number. For example, 19 becomes 1² + 9² = 82. This transformation is the core operation repeated throughout the algorithm.
  2. Initialize two pointers:
  • slow = n
  • fast = n

Both pointers start at the same number. 3. Move the pointers at different speeds:

  • slow moves one step: slow = next(slow)
  • fast moves two steps: fast = next(next(fast))

Moving at different speeds allows us to detect cycles efficiently. 4. Continue looping until slow == fast.

There are two possibilities:

  • If both pointers meet at 1, the sequence reached happiness.
  • If they meet at another value, the sequence is trapped in a cycle.
  1. Return whether the meeting point equals 1.

Why it works

The algorithm works because the sequence of transformations is deterministic. Every number maps to exactly one next number. If the process never reaches 1, it must eventually repeat a previous value, forming a cycle. Floyd's algorithm guarantees that two pointers moving at different speeds will eventually meet inside that cycle. Therefore:

  • Meeting at 1 means the number is happy.
  • Meeting elsewhere means the number is trapped in a loop.

Python Solution

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(number: int) -> int:
            total = 0

            while number > 0:
                digit = number % 10
                total += digit * digit
                number //= 10

            return total

        slow = n
        fast = n

        while True:
            slow = get_next(slow)
            fast = get_next(get_next(fast))

            if slow == fast:
                break

        return slow == 1

The implementation begins with a helper function named get_next, which computes the sum of squared digits. Instead of converting the number into a string, we extract digits mathematically using % 10 and integer division // 10. This avoids unnecessary overhead.

We initialize slow and fast pointers to the starting number n.

Inside the loop:

  • slow advances one transformation at a time.
  • fast advances twice as quickly.

Eventually, one of two outcomes occurs:

  • Both pointers meet at 1, meaning the sequence converged successfully.
  • Both pointers meet elsewhere, meaning we detected a cycle.

The final return statement checks whether the meeting point is 1.

Go Solution

func isHappy(n int) bool {
	getNext := func(number int) int {
		total := 0

		for number > 0 {
			digit := number % 10
			total += digit * digit
			number /= 10
		}

		return total
	}

	slow := n
	fast := n

	for {
		slow = getNext(slow)
		fast = getNext(getNext(fast))

		if slow == fast {
			break
		}
	}

	return slow == 1
}

The Go implementation closely mirrors the Python version. A local helper function computes the next transformed value.

Since Go does not support nested named functions in the same way as Python, we use an anonymous function assigned to getNext.

Integer overflow is not a concern because the sum of squared digits remains very small compared to the int range. Even the largest valid input quickly reduces to much smaller numbers.

Unlike Python, Go uses explicit variable declarations and for loops instead of while.

Worked Examples

Example 1: n = 19

We track the movement of both pointers.

Iteration Slow Fast
Start 19 19
1 82 68
2 68 1
3 100 1
4 1 1

Since both pointers meet at 1, the algorithm returns true.

Transformation details:

  • 19 → 82
  • 82 → 68
  • 68 → 100
  • 100 → 1

Example 2: n = 2

Iteration Slow Fast
Start 2 2
1 4 16
2 16 58
3 37 145
4 58 20
5 89 16
6 145 58
7 42 145
8 20 20

The pointers meet at 20, not 1.

This confirms the sequence entered a cycle:

2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

Therefore, the answer is false.

Complexity Analysis

Measure Complexity Explanation
Time O(log n) Each transformation processes the digits of the number
Space O(1) Only a few integer variables are used

The time complexity comes from computing the sum of squared digits. Processing one number takes O(log n) because the number of digits is proportional to log n.

Although the algorithm may iterate multiple times, values rapidly shrink into a small bounded range. In practice, the runtime is extremely small and effectively constant.

The space complexity is O(1) because Floyd's cycle detection avoids storing visited states. Only the slow, fast, and helper variables are needed.

Test Cases

solution = Solution()

assert solution.isHappy(19) is True   # Provided happy number example
assert solution.isHappy(2) is False   # Provided unhappy number example

assert solution.isHappy(1) is True    # Smallest happy number
assert solution.isHappy(7) is True    # Single-digit happy number
assert solution.isHappy(4) is False   # Known cycle starter

assert solution.isHappy(10) is True   # Reaches 1 quickly
assert solution.isHappy(100) is True  # Contains zeros

assert solution.isHappy(116) is False # Multi-digit unhappy number
assert solution.isHappy(999) is False # Larger unhappy number

assert solution.isHappy(2147483647) is False  # Maximum constraint value
Test Why
19 Validates provided happy-number example
2 Validates provided unhappy-number example
1 Tests immediate success case
7 Tests single-digit happy number
4 Tests known cycle behavior
10 Tests fast convergence to 1
100 Ensures zeros are handled correctly
116 Tests a non-trivial unhappy number
999 Tests larger repeated transformations
2147483647 Tests maximum input boundary

Edge Cases

Input is Already 1

The smallest valid input is 1, which is already a happy number. A careless implementation might unnecessarily enter looping logic or mishandle termination. In this solution, both pointers quickly converge at 1, and the algorithm correctly returns true.

Numbers That Immediately Enter a Cycle

Some numbers, such as 2 or 4, quickly enter repeating loops without ever reaching 1. A naive solution without cycle detection would run forever. Floyd's algorithm guarantees detection because the fast pointer eventually catches the slow pointer inside the repeating cycle.

Large Input Values

The constraint allows numbers as large as 2³¹ - 1. A buggy implementation might worry about excessive runtime or integer overflow. However, summing squared digits rapidly shrinks the number into a much smaller range. For example, even a 10-digit number cannot produce a very large digit-square sum. This implementation safely handles maximum-size inputs without performance issues.