Happy Number

The Digit Dance problem asks whether repeatedly summing the squares of a number's digits will eventually reach 1. This problem tests your ability to detect cycles and apply clever algorithmic thinking.

number theorycycle detectionfast and slow pointersmathematics

Problem Statement

Given a positive integer, perform the following operation repeatedly: replace the number with the sum of the squares of its digits. Continue this process until either the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Determine if the number will eventually reach 1. Return True if it does, and False otherwise.

Example 1

Input: 19

Output: True

1^2 + 9^2 = 82. 8^2 + 2^2 = 68. 6^2 + 8^2 = 100. 1^2 + 0^2 + 0^2 = 1. Therefore, 19 is a Digit Dancing number.

Example 2

Input: 2

Output: False

2^2 = 4. 4^2 = 16. 1^2 + 6^2 = 37. 3^2 + 7^2 = 58. 5^2 + 8^2 = 89. 8^2 + 9^2 = 145. 1^2 + 4^2 + 5^2 = 42. 4^2 + 2^2 = 20. 2^2 + 0^2 = 4. We are back at 4, so this will loop forever and never reach 1.

Constraints

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

Brute Force Approach

A brute-force approach would be like repeatedly calculating the sum of squared digits and storing each result in a list. If we encounter a number we've seen before, we know we're in a cycle and the number won't reach 1. Think of it like visiting cities on a road trip; if you ever return to a city you've already visited, you're stuck in a loop.

TimeO(infinity)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem