Devin's Blog

Happy Number

3 min read

TARGET DECK: Leetcode FILE TAGS: Easy

Intuition

  • A digit will eventually loop back to become itself.
  • That is to say: The following property holds:
    • If a digit’s squares is multiplied by itself enough times, then eventually, you will get the sum equal to 1. Otherwise, it will eventually loop back to become a number “unto itself”.
  • The question then is: why?
    • To understand this, take the largest possible digit. For example, 9, 99, 999, etc.
    • Notice that is 81. Therefore, in the one’s place, any digit smaller than 9 will be at most 81, or some number less than 81. So there are 2 options: Either loop back to some number from 2, to 81, or stop at 1.
  • The Floyds Tortoise and Hare algorithm also works here, wherein you utilize the fact that you loop forever at 1 when you have indeed reached 1, since is always 1, so slow the slow pointer will always eventually catch up to fast.

Info

With this question and others like it, it helps visualizing the entire example, since for example with n = 2, you would have found out the answer if you just kept repeating numbers until the number equaled itself again.

Complexity

Runtime

  • For getNext(): since you are dividing by 10 each time, and so you are doing that = N times, meaning N = .
  • You repeat getNext() a constant number of times (from 4→16→37→58→89→145→42→20→4).

Space

if using Floyds Tortoise and Hare algorithm due to no HashSet.

Code

Using Floyds Tortoise and Hare for Cycle Detection

class Solution:
    def getSquareSum(self, num):
        cur_sum = 0
        while num > 0:
            num, digit  = divmod(num, 10)
            cur_sum += digit ** 2
        return cur_sum
 
    def isHappy(self, n: int) -> bool:
        slow = fast = n
 
        while True:
            slow = self.getSquareSum(slow)
            fast = self.getSquareSum(self.getSquareSum(fast))
 
            if slow == fast:
                break
                
        return slow == 1

Using Divmod

class Solution:
    def getNext(self, num):
        cur_sum = 0
        while num > 0:
            num, digit = divmod(num, 10)
            cur_sum += digit ** 2
        return cur_sum
 
    def isHappy(self, n: int) -> bool:
        while n != 1 and n != 4:
            n = self.getNext(n)
        return n == 1

Using Modulo Arithmetic Instead

class Solution:
    def getNext(self, num):
        cur_sum = 0
        while num > 0:
            num, digit = num // 10, num % 10
            cur_sum += digit ** 2
        return cur_sum
 
    def isHappy(self, n: int) -> bool:
        while n != 1 and n != 4:
            n = self.getNext(n)
        return n == 1
  • Works since // truncates, and % gets the last digit.
  • Alternatively, can probably use Bit Manipulation.

Using Trick: Any Number that is in a Cycle Will Eventually Cycle Back to 4

class Solution:
    def isHappy(self, n: int) -> bool:
        while n != 1 and n != 4:
            n = sum(int(digit) ** 2 for digit in str(n))
        return n == 1

Using HashSet to Store Cycle, and String Set

class Solution:
    def isHappy(self, n: int) -> bool:
        visited = set()
        while n not in visited:
            visited.add(n)
            n = sum(int(digit) ** 2 for digit in str(n))
        return n == 1

Notes

Cards

START Basic Front: Happy Number Back: A number that is squared will always repeat forever, and from 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

END

References

Graph View