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, 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.
Return True if n is a happy number, and False if not.
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
The description was taken from https://leetcode.com/problems/happy-number/.
#O(Log N) Time, O(Log N) Spaceclass Solution: def isHappy(self, n: int) -> bool: seen = set() square_sum = 0 while square_sum != 1: square_sum = 0 while n > 0: square_sum += (n % 10) ** 2 n = n // 10 if square_sum in seen: return False else: n = square_sum seen.add(n) return TrueLet's think about what this problem is actually asking. We are taking a number, initially the input, and then squaring each digit of the number, then adding the sum of the squares together.
We are wanting to then take that sum and doing the same thing until we get one. What if we never get one and get stuck in a cycle? The program will run indefinitely, so we will want to check if we're in a cycle as well.
We can solve this problem by saving square sum values we've seen, and continuously generating each square sum until we either get one or get a cycle.
We can solve this question by using a set to keep track of the square sums. We will initialize our set and the square sum to be zero since we have no sum to process initially.
seen = set() square_sum = 0
We will then make two while loops, the outer will run until we have a square sum equal to one.
while square_sum != 1:
The inner will run while our n, our initial input or the previous iteration’s square sum, has digits left to process. Before each inner loop iteration, we will reset the square sum to zero so that we aren't adding the previous iteration's square sum.
square_sum = 0
The inner loop will square each digit of n and add it to the square sum, then it will chop the digit off of n so that the next digit can be processed during the next iteration. This will run until there are no more digits left to process which will be when n is zero.
while n > 0: square_sum += (n % 10) ** 2 n = n // 10
Once we have our square sum, we are going to see if it is in the set.
If it is, we return false and break out of the loop.
if square_sum in seen: return False
If it is not, we will add it to the set and set n equal to it so it can be processed in the next iteration of the outer loop. Remember, the example given input was 19, we square 1 and 9 and add them together to get 82.
Now we have to input 82 to get it's digits squared and added, that is this step shown below.
else: n = square_sum seen.add(n)
If we have reached the end of the outer loop, it is because we have a square sum that equals one, so we return true.
return True
We may think that this algorithm would be O(N^2) run and space due to the nested while loop, but let's think about what the algorithm is doing. We are finding what the next value for a given number is, and in the worst-case scenario, the number of digits drop by half in each iteration like if we were traversing a BST.
For example, if we had 9999999999999 as an input. We would square each digit getting 8^1+8^1+8^1+8^1+8^1+8^1+8^1+8^1+8^1+8^1+8^1+8^1+8^1 which equals 1053. We went from 13 digits that we needed to process down to 4 that we need to process, a third of the input size.
The amount of space required to store the output values drops the same way. This is why we have O (Log N) time and space.