How do you solve Happy Number?

Use a set to record all numbers encountered during the transformation. In each iteration, compute the sum of squares of digits. If the result is 1, return true. If the number has been seen before, a cycle exists, so return false. This approach guarantees termination and correctness.

What pattern does Happy Number use?

The Pattern: Hash Maps (Cycle Detection via Visited Set) The Heuristic: When a process involves repeated transformations that may cycle, use a hash set to record visited states and detect cycles early, preventing infinite loops and ensuring termination.

Happy Number — Hash Maps

Q: What is the time complexity of Happy Number?

O(log n). Each iteration reduces the number roughly to the sum of squares of its digits, which is bounded by a function of the number of digits. Since the number of digits is O(log n), and each number is unique until a cycle or 1 is found, the total iterations are bounded by a small constant related to digit sums.

Problem

Given an integer n, return true if it is a happy number, and false otherwise. A happy number is defined by repeatedly replacing the number by the sum of the squares of its digits until it equals 1 or it loops endlessly in a cycle that does not include 1.

1 ≤ n ≤ 2³¹ - 1

Example

Input: n = 19

Output: true

Starting with 19, the algorithm computes the sum of squares of digits: 1² + 9² = 1 + 81 = 82. Then for 82: 8² + 2² = 64 + 4 = 68. For 68: 6² + 8² = 36 + 64 = 100. For 100: 1² + 0² + 0² = 1. Since the sequence reaches 1, 19 is a happy number and the function returns true.

Approach

Straightforward Solution

A naive approach would repeatedly compute the sum of squares and check if the number is 1, but without cycle detection, this can lead to infinite loops for unhappy numbers.

Core Observation

The process of repeatedly replacing a number by the sum of the squares of its digits either eventually reaches 1 (happy number) or falls into a cycle that never reaches 1. Detecting this cycle is essential to avoid infinite loops.

Path to Optimal

Preview

The key recognition signals are 'detect cycle' and 'avoid infinite loops'. These indicate using a Hash Map or Set to track previously seen numbers…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a set to record all numbers encountered during the transformation. In each iteration, compute the sum of squares of digits…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log n)

Each iteration reduces the number roughly to the sum of squares of its digits, which is bounded by a function of the number of digits. Since the number of digits is O(log n), and each number is unique until a cycle or 1 is found, the total iterations are bounded by a small constant related to digit sums.

Space

O(log n)

The visited set stores each unique intermediate number encountered. Since numbers are bounded by digit sums, the set size is proportional to the number of unique states, which is O(log n) in the number of digits.

Solution

Python

1class Solution:
  def isHappy(self, n: int) -> bool:
      visit = set()
4
      while n not in visit:
          visit.add(n)
          n = self.sumOfSquares(n)
8
          if n == 1:
              return True
      
      return False
13
  def sumOfSquares(self, n: int) -> int:
      output = 0
      while n:
          digit = n % 10
          digit = digit ** 2
          output += digit
          n = n // 10
      return output

Step-by-Step Solution

1

Track Visited Numbers to Detect Cycles During Transformation

3	`visit = set()`

Objective

To maintain a set of all numbers encountered to detect cycles and prevent infinite loops.

Key Insight

By storing each intermediate number in a set, the algorithm can quickly determine if the current number has appeared before, signaling a cycle. This prevents infinite repetition and ensures the algorithm terminates either by finding 1 or detecting a cycle.

Interview Quick-Check

Core Logic

Using a set to track visited numbers enables O(1) average-time cycle detection, which is essential for correctness and termination.

Common Pitfalls & Bugs

Failing to track visited numbers leads to infinite loops for unhappy numbers.

2

Iteratively Compute Sum of Squares and Check for Happiness or Cycle

To repeatedly transform the number by summing the squares of its digits and check for termination conditions.

3

Calculate Sum of Squares of Digits for Current Number

To compute the sum of the squares of each digit of the current number.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 7 Critical

n = self.sumOfSquares(n)

Update the current number to the sum of the squares of its digits.

This line implements the key state transition by replacing the current number with the sum of squares of its digits, which is the defining operation of the happy number sequence.

Line 9 Critical

if n == 1:

Check if the current number is 1, indicating a happy number.

This check is critical because reaching 1 is the success condition; returning true here ensures correct and efficient termination.

Line 12 Critical

return False

Return false when a cycle is detected (number repeats without reaching 1).

Returning false here correctly identifies that the sequence has entered a cycle, proving the number is unhappy and preventing infinite loops.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why is it necessary to track previously seen numbers when determining if a number is happy?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Happy Number from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Happy Number drill

or drill a free problem

1	`class Solution:`
2	`def isHappy(self, n: int) -> bool:`
3	`visit = set()`
4
5	`while n not in visit:`
6	`visit.add(n)`
7	`n = self.sumOfSquares(n)`
8
9	`if n == 1:`
10	`return True`
11
12	`return False`
13
14	`def sumOfSquares(self, n: int) -> int:`
15	`output = 0`
16	`while n:`
17	`digit = n % 10`
18	`digit = digit ** 2`
19	`output += digit`
20	`n = n // 10`
21	`return output`