Happy Number
Take a positive integer. Replace it by the sum of the squares of its digits. Repeat with the result. The number is called happy if this process reaches 1. Otherwise it loops forever in a cycle that does not contain 1.
Return true if n is a happy number, and false if it is not.
Examples
Input n = 19
Output true
19 -> 82 -> 68 -> 100 -> 1.
Input n = 2
Output false
The chain 2, 4, 16, 37, 58, 89, 145, 42, 20, 4 repeats.
Input n = 1
Output true
1 is already 1.
Constraints
- 1 <= n <= 2,147,483,647
Stuck? Take one hint at a time
Common mistakes
- Running a fixed number of steps such as 100 and calling the result false, which is a guess rather than a proof.
- Turning the number into a string and squaring characters without converting them to digits.
- Waiting for the number to reach 0, which never happens for a positive number.
- In the runner version, forgetting to stop when the fast runner reaches 1.
Questions an interviewer may ask next
- Why can the numbers not grow forever? (A number with d digits maps to at most 81 d, which is below the number itself once d is 4 or more.)
- Count how many happy numbers there are below a million. (Memoize the result per number.)
- What if the rule used cubes instead of squares? Does every start still end in 1 or a loop?
- Prove that every unhappy number ends in the loop 4, 16, 37, 58, 89, 145, 42, 20, 4. (Checking all numbers below 244 shows it.)
n
19
Expected output
true
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.