💬 Discord
Sign In
NeetCode #907LC-202EasyMath & GeometryNC 150NC 250
← Back to All Problems

#907 · #202 · Happy Number(快乐数)

📌 Problem Statement & Constraints

A happy number is a number that eventually reaches 1 when repeatedly replaced by the sum of the squares of its decimal digits; an unhappy number enters a cycle that never contains 1. Given n, return true if it is happy. Constraints: 1 <= n <= 2^31 - 1.

💡 Core Algorithmic Approaches

  1. Define f(x) as the sum of the squares of the digits of x, and iterate x <- f(x).
  2. The sequence is either eventually 1 or eventually periodic, so a cycle detector decides the answer.
  3. Floyd's tortoise-and-hare detects the cycle with O(1) space: advance the slow pointer one step and the fast pointer two steps per iteration, and stop when they meet or the fast pointer reaches 1.
  4. A hash set of previously seen values is simpler to explain but uses O(log n) space; the two-pointer version is the more impressive answer.

💻 Benchmark Python3 Implementation

class Solution:
    def isHappy(self, n: int) -> bool:
        def sqsum(x: int) -> int:
            s = 0
            while x:
                x, d = divmod(x, 10)
                s += d * d
            return s

        slow = n
        fast = sqsum(n)
        while fast != 1 and slow != fast:
            slow = sqsum(slow)             # one step
            fast = sqsum(sqsum(fast))      # two steps
        return fast == 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n) per transformation and the sequence length is bounded by a small constant for 32-bit inputs, so effectively O(1).
💾 Space Complexity
O(1): Floyd's cycle detection uses only two integers.

⚠️ Interview Pitfalls & Follow-ups

  • Looping while n != 1 with no cycle detection: unhappy numbers loop forever, e.g. 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4.
  • Squaring the number instead of each digit: the operation is digit-wise, so n * n is wrong.
  • Advancing the fast pointer only one step: the two pointers would move in lockstep and never meet.
  • Returning slow == 1: the loop may stop because the pointers met, so the correct final test is fast == 1.