Happy Number - Leetcode 202 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Problem Link: neetcode.io/problems/non-cycl...
0:00- Understand problem
2:00 - Drawing solution
4:45 - Coding solution
Leetcode 202
#Coding #Programming #CodingInterview #leetcode #neetcode

[@thelookofdisapproval8234]

1 % 10 = 1 not 0 8:24

[@bluesteel1]

username checks out

[@nos44-]

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

[@nguyen-dev]

The correct sequence in the example starting from 2 is as follow: 2, 4, 16, 37, 58, 89, 145, 42, 20, 4 (cycle). Now "You're gonna have to trust my Math calculations" hahaha

[@kyoungjunhan1098]

@@nguyen-dev Beat it man, everybody makes mistake. Even by coincidence this algorithm works (somehow). Don't forget, he is in Google. Are you? Mistakes don't always define someone's capability. Your attitude does tho, however.

[@nguyen-dev]

@@kyoungjunhan1098 Don't get me wrong! I think you misunderstood my emotion.

[@qazyip]

@@kyoungjunhan1098 I don't think his comment implies anything regarding his intelligence. It's just making fun of a silly mistake that happens to all of us :)

[@sky_9223]

I got confidence with this video. Thanks... God bless you~

[@howheels]

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

[@ThePacemaker45]

Funny cause right before that he says "You're gonna have to trust my math" haha

[@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!

[@Gameplay-ps9ub]

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.

[@sky_9223]

(From Korea) it also looks easier to me, but the above while operation is much faster

[@grandparick3176]

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

[@NeetCode]

Oh no... 😯. You are absolutely correct and thank you so much for catching that! Luckily it does not change the outcome of the solution, but next time I'm just gonna use a calculator lol

[@QuadQuadQuadQuad]

Nice explanation! Enjoying your straightforward explanations!

[@NeetCode]

Thanks!

[@danielsun716]

According to the drawing, we can think of the method of Floyd's Cycle Detection which has been taught by @Neetcode. FYI, kzbin.info/www/bejne/rZu8n62hds2WhM0 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 = sumOfSquare(sumOfSquare(fast)) return fast == 1

[@markolainovic]

Awesome, thanks!

[@illu1na]

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

[@christopherperezlebron2434]

how would you describe the time and space complexity?

[@pauljones9150]

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.

[@ayacyte443]

You can also just check that if n !=1, break if the number is already in the list

[@NasifIstiak]

That's what I did after observing the result of a few inputs and got confused as to why all the solutions on LC are with hashmaps and so on.. I thought it was labeled easy because you just had to find a loophole in the problem or something 💀💀 My code basically devolves into doing the process and checking if the number is 4, and to return false if so.

[@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?

[@enigmatekinc3573]

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)

[@amrholo4445]

Thanks a lot, sir

[@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

[@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 💀💀

[@indrapreetsingh9680]

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.

[@sanooosai]

Thank you

[@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 ))

[@nishansinghdhillon1714]

What will be the time complexity ? Since we don't know how long it goes to reach a repetition or 1

[@MinhNguyen-lz1pg]

Check LC Solution, its free man

[@ssgojekblue]

The fast and slow pointer video explanation is required

[@tricktreat7941]

1 % 10 is not 0, it is 1.

[@SameenIslam]

This can also be solved in a similar way using the fast and slow pointers technique.

[@piuskitheru3213]

paste your code

[@tiyaaaa3917]

t is logn？

[@Ivan-ek6kg]

Have a question? why we use set ? list does not work?

[@NeetCode]

Set in this case is a hashset, so it will be more efficient that a list

[@spiffylogic]

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

[@sleepypanda7172]

This man is a genius!

[@Cruzylife]

nuts that this is an easy

[@NeetCode]

agreed

[@musicsangram3637]

What about time complexity?!! We know sumOfSquares is O(log n) but how many times the loop runs in worst case? One weak bound is O(n) leading to O(nlogn) complexity but I think it's better than that.

[@zis492]

I think u can break the loop when n=1 And then return true else false

[@Manish-fd5jb]

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)

[@bandhammanikanta]

Great explanation. (Clap) to the final comment.

[@maganaluis92]

How is 3^2 + 7^2 = 30?

[@NeetCode]

yes you are correct, sorry my brain was lagging for some reason haha. Luckily the algorithm and outcome is still correct though.

[@taniskaadhikari6666]

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

[@xiwang7614]

I see that too

[@LazyLatte_27]

What is the time complexity?

[@yaadata]

O(log(n)) . edit: this solution does not use constant space

[@LazyLatte_27]

@@yaadata Thank you

[@orellavie6233]

Why is that O(logn)? I don't see where we cut each work by 2 each time. Thanks

[@mhmdshaaban]

37 ---> 3 ^ 2 + 7 ^ 2 = 58 not 30 3:22

[@dilippokhrel4009]

🤣my algorithm is while doing 30 iterations if the value converges to one return True, if not then simply return False. This algorithm beats 98.6 in speed and 99.4 in space one lol

[@sharoncohen318]

37 -- 9 + 49 -- 58, you did 7* 3 instead of 7*7 lol

[@ayushrawat9267]

code in C++: int sumOfSq(int n ){ int sq =0; while(n > 0){ int ls = n%10; sq += ls*ls; n /= 10; } return sq; } bool isHappy(int n) { if(n == 1){ return true; } unordered_set hset; while(!hset.count(n)){ hset.insert(n); n = sumOfSq(n); if(n==1 ){ return true; } } return false; }

[@TalMarci]

how do you know that we always get a cycle? I understand that it's true, but what was your intuition? without knowing this as a complete fact this question is not solvable. unless there's a nice way to prove it using this fact as a guest without proving feels like cheating..)

[@mukeshsirvi5152]

Hey you made a mistake in square in digits of 37

[@StfuSiriusly]

yes dude, there are already a bunch of comments about it..

[@huangCAnerd]

Hi NeetCode, this solution no longer passes on LeetCode due to TLE (time limit exceeded) 😢 Edit: I mistyped the solution and it actually works.

[@akrammohamed8374]

7 squared is 49 not 21

[@qwertythefish6442]

3 ^ 2 + 7^2 = 58 not 30

[@SomneelMaity]

C++ Recursive Solution class Solution { public: bool isHappy(int n) { int sum = 0; if(n == 0) { return false; } if(n == 1) { return true; } if(n < 7 && n > 1) return false; while(n != 0) { int m = n % 10; n = n / 10; sum += m*m; } return isHappy(sum); } };

[@mirshodoripov1035]

1%10 = 1 not 0

[@user-vy7gk2qn9l]

i=0 s=set() while n!=1: z=0 for x in str(n): z+=int(x)**2 n=z i+=1 s.add(z) if len(s) != i: return False if n==1: return True

[@zaph254]

3 squared plus 7 squared is 58 not 30, kzbin.info/www/bejne/opvdaWiYrbSMgJI

[@saimmehmood6936]

I don't think we necessarily need the set datatype here. List can do the job with less memory consumption. Or actually, the use of set might be wrong as it does not allow duplicates and that's what we are trying to look for in the loop.

[@weaammohamed8992]

and regarding to the duplicate question, Here we will stop the loop immediately once we know that current item already saved in the set so no need to save it or care about duplicating problem

[@weaammohamed8992]

​@theraplounge Yes, space complexity is the same so we're comparing between time complexity

[@max1mu5dc]

Dunno who made this Leetcode problem. The problem statement is so dumb.

[@EduarteBDO]

I did this question a bit different but with the same logic class Solution: def isHappy(self, n: int) -> bool: visit = set() while n != 1: sum,num = 0,n while num > 0: sum += (num%10)**2 num //= 10 n = sum if n in visit: return False visit.add(n) return True

[@inweirder1144]

THE REAL HAPPY NUMBER WAS FOUND it's 7 this code will work no need in set or slow/fast pointer const isHappy = function(n) { let number = n let square = 0 while (number >= 10) { while(number > 0) { square += (number % 10) ** 2 number = Math.floor(number / 10) } number = square square = 0 } // 7 is real happy number :) return number === 1 || number === 7 };

[@pauljones9150]

This is the optimal code. It uses the fact that all numbers loop through 1 or 4. See oeis.org/A007770 or en.wikipedia.org/wiki/Happy_number class Solution: def isHappy(self, n: int) -> bool: while n not in [1, 4]: n = sum(int(d)**2 for d in str(n)) return n==1

[@chirpy7961]

Can you please tell me about time and memory complexity of this solution?..

[@elitefusion750]

@@chirpy7961 O(log(n)) . edit: this solution does not use constant space