Happy Number
A happy number is 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. Write a function that takes an integer as input and returns True if it is a happy number, and False otherwise.
Constraints:
- 1 <= n <= 2^31 - 1
- Input will not be 0
Examples:
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
Input: 20
Output: False
Explanation: 2^2 + 0^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, and we are back to where we started
Solutions
Hash Set
We use a hash set to keep track of the numbers we have seen so far. We keep replacing the number with the sum of the squares of its digits until we reach 1 or we see a number we have seen before. If we reach 1, we return True, otherwise we return False.
def isHappy(n:
int) -> bool:
seen = set(); while n != 1 and n not in seen:
seen.add(n); n = sum(int(i) ** 2 for i in str(n)); return n == 1Follow-up:
What if we want to find all happy numbers up to a given number?
