202. Happy Number

Intuition

A happy number eventually reaches 1; an unhappy one enters a cycle. Detect the cycle using Floyd's tortoise-and-hare algorithm on the sequence of digit-square-sum values. If the slow and fast pointers ever point to 1, it's happy.

Algorithm

1Define Next(n): sum of squares of digits of n.
2slow = Next(n), fast = Next(Next(n)).
3While slow != fast: slow = Next(slow), fast = Next(Next(fast)).
4Return slow == 1.

Example Walkthrough

Input: n = 19

1.19 -> 1^2+9^2=82 -> 8^2+2^2=68 -> 6^2+8^2=100 -> 1^2+0+0=1. Happy!

Output: true

Common Pitfalls

•A HashSet of visited values also works and may be clearer; Floyd's is O(1) space.

202.cs

// Approach: Apply Floyd's cycle-detection (slow/fast pointers) on the digit-square-sum sequence.
// A non-happy number always enters a cycle that does not include 1.
// Slow advances one step; fast advances two steps per iteration.
// If they meet at 1, the number is happy. If they meet at any other value, a cycle exists.
// This avoids storing the visited set that a hash-based approach would need.
// Time: O(log n) per step (digit sum computation). Space: O(1).

public class Solution
{
    public bool IsHappy(int n)
    {
        int slow = SquaredSum(n);
        int fast = SquaredSum(SquaredSum(n));

        while (slow != fast)
        {
            slow = SquaredSum(slow);
            fast = SquaredSum(SquaredSum(fast));
        }

        return slow == 1;
    }

    private int SquaredSum(int n)
    {
        int sum = 0;
        while (n > 0)
        {
            sum += (int)Math.Pow(n % 10, 2);
            n /= 10;
        }
        return sum;
    }
}

Was this solution helpful?