Happy Number

Easy

Fast & Slow Pointers

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 otherwise.

This problem demonstrates that the fast & slow pointer technique applies beyond linked lists! The sequence of digit-square-sums forms an implicit linked list. If the number is not happy, the sequence will cycle, which we can detect using Floyd's algorithm.

Example 1

Input: n = 19

Output: true

Explanation: 1^2 + 9^2 = 82, 8^2 + 2^2 = 68, 6^2 + 8^2 = 100, 1^2 + 0^2 + 0^2 = 1

Example 2

Input: n = 2

Output: false

Explanation: The sequence starting from 2 enters a cycle: 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 (cycle)

Constraints

•1 <= n <= 2^31 - 1

Show Hints (4)

Hint 1: The key insight is that the sequence of sums will either end at 1 or enter a cycle. Sound familiar?

Hint 2: You could use a HashSet to track seen numbers. But can you solve it with O(1) space?

Hint 3: Think of each number as a node, and the sum-of-squares as a "next" pointer.

Hint 4: Apply the same principle as cycle detection in a linked list!

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?