Happy Number - Leetcode 202 - Python

0:00- Understand problem
2:00 - Drawing solution
4:45 - Coding solution

Leetcode 202
#Coding #Programming #CodingInterview #leetcode #neetcode

[nos-]

JUST SECONDS AFRER HE SAID : " You'r gonna have to trust my Math calculations "
( 3 * 3 ) + ( 7 * 7 ) = 30 🤣

[howheels]

3:20 "Sum of squares of 37 is 9 and 21" - Might want to double-check that answer! 😆

[amathis]

You can also convert n -> str -> int array. Beats 90% of other submissions.

class Solution(object):
def isHappy(self, n):
seen = set()
while n not in seen:
seen.add(n)
arr = [int(c) for c in str(n)]
n = sum([v**2 for v in arr])
if n == 1:
return True
return False

1. Create hash set
2. Loop while n is not in hash set (seen)
3. Add n to hash set
4. create a list comprehension that is converting n to a string and then adding integer version of each string character into a list.
5. create a list comprehension to loop through each integer, square it, and return the values to sum() to get the total
6. check to see if n now equals 1. If it does, return True.. it's a happy number.
7. If not, return to step 2. If at step 2, it's determined the number has been seen before, break the loop.
8. Return false.. loop was broken and happy number wasn't found.

[Gameplay-psub]

Regarding the helper function:
If "n" is guaranteed to be a "valid" integer you can also do it like this:
def helper(n):
return sum[int(d)**2 for d in str(n)]

For me it's easier.

[LunaFlahy]

I think this was one of the early videos on your channel. I have to say your skills grow up a lot after two years!! Still appreciate the content!

[danielsun]

Whatever the start position of slow and fast, if there is a cycle, fast and slow gonna meet at one point. But we should notice that fast cannot be initilized as n, due to the while loop condition.

def isHappy(self, n: int) -> bool:
# Floyd's Cycle Detection
def sumOfSquare(num):
output = 0
while num:
digit = num % 10
digit = digit ** 2
output += digit
num = num // 10
return output

slow = n
fast = sumOfSquare(n)
# when fast = 1 stop and slow == fast stop
while fast != 1 and slow != fast:
slow = sumOfSquare(slow)
fast =
return fast == 1

[pauljones]

Based on the Wikipedia page, all numbers will loop back to 1 or 4. If you do a branch and check if n in [1, 4]: break, then return n==1 you should be fine. Also, you can use list comprehension like others suggested to solve this question easily.

[grandparick]

Isn't the sum of 3 squares plus 7 squares equals= 58?.

[digestable_bits]

2 additional points!
1. (stolen from comment section of leetcode) the reason we are guaranteed to hit a duplicate number(1 or some other number) after finite iterations:
integer max value = ‭2 147 483 647(assuming 32 bit)‬, then the number that would give us the maximum sum of squares is 1 999 999 999, with that sum being (1*1)*1 + (9*9)*9 = 724, therefore any valid integer would give us a sum of squares in the range [1, 724], meaning that we would at most need 724 iterations before reaching a duplicate that is not 1.
2. we can also use slow&fast pointer approach for this problem

[QuadQuadQuadQuad]

Nice explanation! Enjoying your straightforward explanations!

[Manish-fdjb]

Another solution for the problem. Its based on an observation that sum of squares at some point reaches number 4 (If its cyclic).

class Solution:
def isHappy(self, n: int) -> bool:
def sum_of_squares(n):
total = 0
while n:
digit = n % 10
total += digit**2
n = n // 10
return total

digits_sum = sum_of_squares(n)
while True:
if digits_sum == 4:
return False
elif digits_sum == 1:
return True

digits_sum = sum_of_squares(digits_sum)

[FUNTasticFlutter]

Nice job mate!
my solution is slightly less efficient both in runtime and mem but simple o implement, my sumOfSquares is different
def sumOfSquares(self, n: int) -> int:
output = 0
numStr = str(n)
for char in numStr:
digit=int(char)
output += digit**2
return int(output)

[NasifIstiak]

As someone else in the comments pointed out, if the numbers never cycle to 1, they do cycle back to 4.

My code basically devolves into doing the process and checking if the number is 4, and to return false if so. It usually takes about 5-10 iterations at most.

I observed the result of a few inputs and got confused as to why all the solutions on LC are with hashmaps, recursion, floyd's algo and so on.. I thought it was labeled easy because you just had to find a loophole in the problem or something 💀💀

[BlumChoi]

Is it not possible that we will be stuck in an infinite loop? Why is it understood that if we sum the digits of a number we are bound to repeat the same value eventually?

[RazmikPoghosyan]

Thanks to this problem, I found a bug in Leetcode. Tried to solve with recursion and a second parameter I used some kind of memo with list as a default value (like `visit` here). And turned out my 3rd test was always failing, because test was not creating new object for all tests separately as they do (as far as I get) for other problems, where memoization can be used ))

[christopherperezlebron]

how would you describe the time and space complexity?

[illuna]

Can someone explain to me what the time complexity is? None of the stack overflow or leetcode solution properly explain what time complexity for happy number is

[indrapreetsingh]

Thanks for the clear explanation as always! :)
We can also return false if set size < no.of times the while loop has run instead of running the while loop until we find an already existing element. Although both ways the time complexity is O(n) only. The count check will require an extra variable though.

[taniskaadhikari]

for your kind information 37 would be 3*3+7*7=58 not 30 (3:20)

[spiffylogic]

No need to check n==1 inside the while loop. Just return n==1 at the end.