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.
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.
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
According to the drawing, we can think of the method of Floyd's Cycle Detection which has been taught by @Neetcode. FYI, ruclips.net/video/wjYnzkAhcNk/видео.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
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.
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
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
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)
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?
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 💀💀
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 ))
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
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
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 };
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.
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
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
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
According to the drawing, we can think of the method of Floyd's Cycle Detection which has been taught by @Neetcode. FYI, ruclips.net/video/wjYnzkAhcNk/видео.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!
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.
Nice explanation! Enjoying your straightforward explanations!
Thanks!
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
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
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)
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!
how would you describe the time and space complexity?
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
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 💀💀
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)
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?
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 ))
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.
No need to check n==1 inside the while loop. Just return n==1 at the end.
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;
}
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
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.
t is logn？
nuts that this is an easy
agreed
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
Hi NeetCode, this solution no longer passes on LeetCode due to TLE (time limit exceeded) 😢
Edit: I mistyped the solution and it actually works.
Thanks a lot, sir
This can also be solved in a similar way using the fast and slow pointers technique.
paste your code
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.
Thank you
for your kind information 37 would be 3*3+7*7=58 not 30 (3:20)
I see that too
I think u can break the loop when n=1
And then return true else false
The fast and slow pointer video explanation is required
I miss the old neetcode, straight from the 'Go Kanye....
37 ---> 3 ^ 2 + 7 ^ 2 = 58 not 30
3:22
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..)
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
Hey you made a mistake in square in digits of 37
yes dude, there are already a bunch of comments about it..
This man is a genius!
Great explanation. (Clap) to the final comment.
37 -- 9 + 49 -- 58, you did 7* 3 instead of 7*7 lol
3 ^ 2 + 7^2 = 58 not 30
7 squared is 49 not 21
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=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
🤣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
1%10 = 1 not 0
3 squared plus 7 squared is 58 not 30, ruclips.net/video/ljz85bxOYJ0/видео.html
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
Dunno who made this Leetcode problem. The problem statement is so dumb.
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
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
};