Happy Number

Explanation & Solution

Description

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Input: n = 19

Output: true

Explanation:

1² + 9² = 82

8² + 2² = 68

6² + 8² = 100

1² + 0² + 0² = 1

Fast and Slow Pointers pattern

Create a getNext(num) function that computes the sum of the squares of the digits of num
Extract each digit using num % 10, square it, and add it to a running sum
Divide num by 10 (integer division) to move to the next digit

If the loop exits because fast === 1, the number is happy — return true
If the loop exits because slow === fast (and it's not 1), a cycle was detected that doesn't include 1 — return false

The sequence of digit-square sums either reaches 1 or enters a cycle — it cannot grow to infinity (the maximum sum for a number with d digits is 81d, which is always smaller than the original number for large values)
This is the same Floyd's Cycle Detection technique used for linked lists, applied to an implicit sequence

Time

O(log n)the number of digits determines how quickly the sequence converges

Space

O(1)only two variables are used, no hash set needed