Link: https://leetcode.com/problems/happy-number/
Solution:
Topics: linked list
Intuition
Cool problem demonstrating the use of an implicit linked list. The naive solution would of course use more memory as the cycle detection would be handled by a set which is o(n) memory.
Instead we treat this like a linked list and use a fast/slow pointer to handle cycle detection in o(1) memory.
Implementation
def happy_number(n):
def process(num):
num = str(num)
num = [int(digit)**2 for digit in num]
return sum(num)
slow = n
fast = n
while slow != 1 and fast != 1:
slow = process(slow)
fast = process(process(fast))
if slow == fast and slow != 1:
return False
return True
#time: o(logn) just remember logn.
#memory: o(1)Mnemonic
We are in number land. Each number is linked to the next number in a list. Its happy if the list is straight and sad if the list has a loop.
Visual
