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
@@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.
@@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 :)
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.
Or: def isHappy(self, n: int) -> bool: happyStore = {} while n != 1: newSum = 0 for number in str(n): newSum += int(number) * int(number) n = newSum if n in happyStore: return False else: happyStore[n] = True return True
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.
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.
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.
According to the drawing, we can think of the method of Floyd's Cycle Detection which has been taught by @Neetcode. FYI, th-cam.com/video/wjYnzkAhcNk/w-d-xo.html 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
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
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
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)
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 💀💀
- **Introduction**: - Discussing Leetcode problem 202: Happy Number. - Objective: Determine if a number is "happy." - **Explanation of Happy Number**: - Given an input number `n`, return `true` if it's a happy number, `false` otherwise. - To check if a number is happy: - Take each digit, square it, and sum the squares. - Repeat the process until the number reaches 1 (happy) or gets stuck in a loop (unhappy). - **Example with 19**: - Start with 19: - 1² + 9² = 82. - 8² + 2² = 68. - 6² + 8² = 100. - 1² + 0² + 0² = 1 (Happy number). - If it reaches 1, it's happy. - If it loops endlessly, it's not. - **Example with 2 (Unhappy Number)**: - Start with 2: - 2² = 4. - 4² = 16. - Sum of squares of 16 gives 37, then it repeats and forms a cycle. - Since it doesn’t reach 1, return `false` (Unhappy number). - **Using a Hash Set**: - To detect cycles efficiently, use a hash set to track visited numbers. - If a number is revisited (without reaching 1), it's stuck in a loop (unhappy). - **Helper Function**: - A helper function computes the sum of squares of digits: - Modulo operation (`n % 10`) to get the digit. - Square the digit and sum the squares. - Divide by 10 to remove processed digits. - **Termination Condition**: - If `n` equals 1, return `true`. - If a value repeats without reaching 1, return `false`. - **Efficiency**: - The solution has a memory complexity of O(n) because of the hash set. - A more efficient approach uses a cycle detection algorithm, similar to detecting cycles in a linked list. - **Conclusion**: - The problem is fundamentally about cycle detection. - A more efficient solution could be implemented using linked list cycle detection techniques. - **Closing**: - Encourages viewers to like, subscribe, and return for more content.
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)
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 ))
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
Dont think its simple to compute complexity of solution. if there are n digits, max next value is 81n, which may have more digits, so it would depend on the largest cycle possible, using the number 99999999 in my code I get 13 runs of the loop, so it went through 13 distinct numbers and all their digits. Lets say largest cycle size to find is m, assume that largest digit size is d (would maybe be some function of n), then our worst case complexity is O(md)
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?
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.
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.
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
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..)
🤣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
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.
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
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 };
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
![ประสบการณ์ จ้าง Developer ที่ผมจะไม่มีวันลืม [ภาค1]](http://i.ytimg.com/vi/bzivN4KDg-k/mqdefault.jpg)
1 % 10 = 1 not 0
8:24
username checks out
JUST SECONDS AFRER HE SAID : " You'r gonna have to trust my Math calculations "
( 3 * 3 ) + ( 7 * 7 ) = 30 🤣
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
@@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.
@@kyoungjunhan1098 Don't get me wrong! I think you misunderstood my emotion.
@@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 :)
I got confidence with this video. Thanks... God bless you~
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.
Or:
def isHappy(self, n: int) -> bool:
happyStore = {}
while n != 1:
newSum = 0
for number in str(n):
newSum += int(number) * int(number)
n = newSum
if n in happyStore:
return False
else:
happyStore[n] = True
return True
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.
(From Korea) it also looks easier to me, but the above while operation is much faster
3:20 "Sum of squares of 37 is 9 and 21" - Might want to double-check that answer! 😆
Funny cause right before that he says "You're gonna have to trust my math" haha
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.
You can also just check that if n !=1, break if the number is already in the list
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.
According to the drawing, we can think of the method of Floyd's Cycle Detection which has been taught by @Neetcode. FYI, th-cam.com/video/wjYnzkAhcNk/w-d-xo.html
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
Awesome, thanks!
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!
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
Nice explanation! Enjoying your straightforward explanations!
Thanks!
Isn't the sum of 3 squares plus 7 squares equals= 58?.
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
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)
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 💀💀
- **Introduction**:
- Discussing Leetcode problem 202: Happy Number.
- Objective: Determine if a number is "happy."
- **Explanation of Happy Number**:
- Given an input number `n`, return `true` if it's a happy number, `false` otherwise.
- To check if a number is happy:
- Take each digit, square it, and sum the squares.
- Repeat the process until the number reaches 1 (happy) or gets stuck in a loop (unhappy).
- **Example with 19**:
- Start with 19:
- 1² + 9² = 82.
- 8² + 2² = 68.
- 6² + 8² = 100.
- 1² + 0² + 0² = 1 (Happy number).
- If it reaches 1, it's happy.
- If it loops endlessly, it's not.
- **Example with 2 (Unhappy Number)**:
- Start with 2:
- 2² = 4.
- 4² = 16.
- Sum of squares of 16 gives 37, then it repeats and forms a cycle.
- Since it doesn’t reach 1, return `false` (Unhappy number).
- **Using a Hash Set**:
- To detect cycles efficiently, use a hash set to track visited numbers.
- If a number is revisited (without reaching 1), it's stuck in a loop (unhappy).
- **Helper Function**:
- A helper function computes the sum of squares of digits:
- Modulo operation (`n % 10`) to get the digit.
- Square the digit and sum the squares.
- Divide by 10 to remove processed digits.
- **Termination Condition**:
- If `n` equals 1, return `true`.
- If a value repeats without reaching 1, return `false`.
- **Efficiency**:
- The solution has a memory complexity of O(n) because of the hash set.
- A more efficient approach uses a cycle detection algorithm, similar to detecting cycles in a linked list.
- **Conclusion**:
- The problem is fundamentally about cycle detection.
- A more efficient solution could be implemented using linked list cycle detection techniques.
- **Closing**:
- Encourages viewers to like, subscribe, and return for more content.
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)
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 ))
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
Dont think its simple to compute complexity of solution. if there are n digits, max next value is 81n, which may have more digits, so it would depend on the largest cycle possible, using the number 99999999 in my code I get 13 runs of the loop, so it went through 13 distinct numbers and all their digits. Lets say largest cycle size to find is m, assume that largest digit size is d (would maybe be some function of n), then our worst case complexity is O(md)
No need to check n==1 inside the while loop. Just return n==1 at the end.
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?
oeis.org/A003621/a003621.pdf
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.
how would you describe the time and space complexity?
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;
}
Hi NeetCode, this solution no longer passes on LeetCode due to TLE (time limit exceeded) 😢
Edit: I mistyped the solution and it actually works.
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.
1 % 10 is not 0, it is 1.
But how do you know if we are in an infinite loop, it is because we are stuck in a cycle, not because the result will be some random numbers forever?
You you're in a loop, if the calculated number is already in the set.
for your kind information 37 would be 3*3+7*7=58 not 30 (3:20)
I see that too
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
What will be the time complexity ? Since we don't know how long it goes to reach a repetition or 1
Check LC Solution, its free man
Have a question? why we use set ? list does not work?
Set in this case is a hashset, so it will be more efficient that a list
I think u can break the loop when n=1
And then return true else false
Thank you
Thanks a lot, sir
This can also be solved in a similar way using the fast and slow pointers technique.
paste your code
The fast and slow pointer video explanation is required
nuts that this is an easy
agreed
37 ---> 3 ^ 2 + 7 ^ 2 = 58 not 30
3:22
t is logn？
How is 3^2 + 7^2 = 30?
yes you are correct, sorry my brain was lagging for some reason haha. Luckily the algorithm and outcome is still correct though.
This man is a genius!
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..)
n is in the following range according to leetcode --> 1
Hey you made a mistake in square in digits of 37
yes dude, there are already a bunch of comments about it..
How this is Easy problem?
37 -- 9 + 49 -- 58, you did 7* 3 instead of 7*7 lol
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
3 ^ 2 + 7^2 = 58 not 30
Bro : Trust my math
* Bro messed up the math immediately after
Still bro is a legend... 😛 # coding humour
I miss the old neetcode, straight from the 'Go Kanye....
7 squared is 49 not 21
Great explanation. (Clap) to the final comment.
What is the time complexity?
O(log(n))
.
edit: this solution does not use constant space
@@yaadata Thank you
Why is that O(logn)? I don't see where we cut each work by 2 each time. Thanks
🤣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
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);
}
};
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.
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
@theraplounge Yes, space complexity is the same so we're comparing between time complexity
1%10 = 1 not 0
Dunno who made this Leetcode problem. The problem statement is so dumb.
Here is a much easier way to compute the sum of the squares
def getSumOfSquares(n):
theSum = 0
for i in str(n):
theSum += int(i)**2
return theSum
3 squared plus 7 squared is 58 not 30, th-cam.com/video/ljz85bxOYJ0/w-d-xo.html
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
};
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
Can you please tell me about time and memory complexity of this solution?..
@@chirpy7961 O(log(n))
.
edit: this solution does not use constant space