#202

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Happy Number

Determine if a number is happy by repeatedly summing squares of digits using two-pointer scanning to detect cycles efficiently.

hash table math two pointers

Problem Statement

Write a function that determines if a given positive integer n is a happy number. A happy number is defined by repeatedly replacing n with the sum of the squares of its digits until it equals 1 or loops endlessly in a cycle.

Return true if n is a happy number and false if it enters a cycle that never reaches 1. For example, 19 is happy because 1^2 + 9^2 = 82, 8^2 + 2^2 = 68, 6^2 + 8^2 = 100, and 1^2 + 0^2 + 0^2 = 1. Conversely, numbers like 2 are not happy because they enter cycles that never reach 1.

Examples

Example 1

Input: n = 19

Output: true

12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

Example 2

Input: n = 2

Output: false

Example details omitted.

Constraints

1 <= n <= 231 - 1

Solution Approach

Use Hash Table to Track Seen Numbers

Iterate by replacing n with the sum of squares of its digits and store each result in a hash set. If a number repeats, a cycle exists and the function returns false. If 1 is reached, return true.

Two-Pointer Cycle Detection

Apply the slow and fast pointer approach where slow advances one sum-of-squares step and fast advances two. If slow equals fast, a cycle is detected. Return true only if 1 is reached; otherwise, return false.

Optimize Digit Square Computation

Precompute squares of digits 0-9 to avoid recalculating each digit's square repeatedly. This reduces overhead in both hash table and two-pointer approaches, improving performance in large n.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of steps to either reach 1 or detect a cycle, roughly O(log n) per iteration because sum of squares reduces the number magnitude. Space complexity is O(log n) for hash table storage or O(1) using two-pointer cycle detection.

What Interviewers Usually Probe

Expect candidate to identify the repeated digit cycle problem and suggest a hash set or two-pointer approach.
Watch if the candidate optimizes digit square computation to reduce unnecessary calculations.
Look for clear reasoning on terminating conditions: reaching 1 versus detecting a loop.

Common Pitfalls or Variants

Common pitfalls

Not handling cycles correctly, leading to infinite loops in naive implementations.
Recomputing digit squares every iteration instead of caching, causing inefficiency.
Assuming all numbers eventually reach 1 without verifying cycles, leading to incorrect true returns.

Follow-up variants

Determine if a number is unhappy by returning the cycle sequence instead of a boolean.
Find all happy numbers in a range from 1 to N using the same sum-of-squares approach.
Compute happiness under a different base system, e.g., base-16 digits, using the same two-pointer pattern.

FAQ

What is the main pattern to detect cycles in Happy Number?

The key pattern is two-pointer scanning (slow and fast) or hash table tracking to identify repeated sums that indicate a cycle.

Can we solve Happy Number without extra space?

Yes, using the slow and fast pointer approach, we can detect cycles in O(1) space while still identifying happy numbers correctly.

Why precompute digit squares for Happy Number?

Precomputing 0-9 squares avoids repeated calculation and reduces the per-iteration cost when summing digit squares.

What happens if n is already 1?

If n starts as 1, it is immediately identified as happy and the function returns true without further computation.

How to handle numbers that never reach 1?

Detect cycles using either a hash set of seen numbers or the two-pointer technique, and return false when a cycle is detected.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def isHappy(self, n: int) -> bool:
        vis = set()
        while n != 1 and n not in vis:
            vis.add(n)
            x = 0
            while n:
                n, v = divmod(n, 10)
                x += v * v
            n = x
        return n == 1

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def isHappy(self, n: int) -> bool:
        vis = set()
        while n != 1 and n not in vis:
            vis.add(n)
            x = 0
            while n:
                n, v = divmod(n, 10)
                x += v * v
            n = x
        return n == 1

Continue Practicing

#189 rotate array #166 fraction to recurring decimal #160 intersection of two linked lists