LeetCode #202 Happy Number

Easy

Problem

Write an algorithm to determine if a number 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, and 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 numbers.

Example:

Input: 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

Solution — Hash Set

Use a hash set to record all calculated numbers, and return false once there is a number has already appeared before.

Complexity

It’s too hard for me to estimate the executions of the while loop on line 14. But if we assume the while loop executes k times, the time complexity will be O(kd)/O(kd*logk) if d denotes to the counts of digits of n in average/worst cases of search and insertion operations of hash sets.

It’s trivial that space complexity is O(k) for maintaining the hash set.

Solution — Two pointers

Just link manipulations in linked list. We can use a faster pointer and a slower pointer to check if there is a cycle, which means the same calculated number appeared again.

Complexity

It’s the same hard for me to estimate executions of while loop on line 15, so we assume it’s k. Therefore, the time complexity is O(kd) if d denotes to counts of digits of n.

It’s obviously that it uses only O(1) extra space.