Skip to content

202. Happy Number

Summary

Solution Approach Explanation Time Complexity Space Complexity
Brute Force with Set Each iteration computes sum of squares in \(O(\log n)\) time; number of iterations is constant as numbers quickly reduce to a small cycle or 1, so overall \(O(\log n)\) time and \(O(1)\) space. \(O(\log n)\) \(O(1)\)
Floyd's Cycle Detection Use slow and fast pointers to detect cycles without extra space. \(O(\log n)\) \(O(1)\)

Implementation

Brute Force with Set
class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()

        while n not in seen:
            seen.add(n)
            n = self.getNext(n)

        return n == 1

    def getNext(self, n: int) -> int:
        nextNumber = 0
        while n != 0:
            nextNumber += (n % 10) ** 2
            n //= 10
        return nextNumber
Fast Slow Pointers
class Solution:
    def isHappy(self, n: int) -> bool:
        slow = n
        fast = self.getNext(n)

        while slow != fast:
            slow = self.getNext(slow)
            fast = self.getNext(self.getNext(fast))

        return fast == 1

    def getNext(self, n: int) -> int:
        nextNumber = 0
        while n != 0:
            nextNumber += (n % 10) ** 2
            n //= 10
        return nextNumber
```