How To Solve LeetCode Happy Number | Understanding Algorithms

hey everybody in this video we're going to talk about the lead code problem called happy number so let's get started by reading the problem so we're asked to write an algorithm to determine if a number n is happy so we're going to have a parameter called n which is going to be a number now let's find out what they mean by happy so a happy number is a number defined by the following process starting with any positive integer replace the number by the sum of the squares of its digits and repeat the process until the number equals one where it'll stay or it loops endlessly in a cycle which does not include one and those numbers for which this process ends in one are happy numbers and ultimately what we need to do is we need to return a boolean value either true if n is a happy number and false if it's not now if the process for defining a happy number is a little bit confusing to you i think it'll help to look at a couple examples so here let's say that we're given the number 19 so n will equal 19. what we need to do is we need to break down that number into its digits so we'll take the 1 and then we'll take the 9 and we'll square each of those so here you can see 1 squared plus 9 squared is going to give us 82. and then once we have that 82 we're going to need to take that 82 break that one down into its individual digits and square each of them and get the new sum from that and then we repeat this process so now we have 6 squared plus 8 squared or 36 plus 64 is going to give us 100 and then we'd take the 100 break that one down into its individual digits which would give us 1 squared plus 0 squared plus 0 squared which is going to equal 1. and since we were able to arrive at 1 through this entire process the number 19 which we started with is in fact a happy number and so our function is going to return true now let's look at a case in which we have a number that's not a happy number so in this example here we have the number 18 as the input if we go through our process we take the 1 and the 8 from the 18 we'd square each of them and we'd get 65 and then i'll go through the process a little bit more quickly here because with the 18 we end up with a lot more steps but you can see that we take each of the sums that we get break out the individual numbers square them add them up to get a new sum and we keep going all the while looking to see if at some point we get the number 1 and here you can see we're still going and we haven't arrived at 1 yet and here notice what happens at this point with the number 16 if we break it down we get a 1 squared plus 6 squared which equals 37 and as you can see we've seen that number before which means that we're going to be stuck in an endless loop here right because once we get that 37 if we break it down again we're going to just be going through all the same calculations that we've done before already so here we have a number that's not happy going through these examples you can see that there are two big main things that we need to do in our algorithm the first one is that we're going to need a process for breaking a number down into its digits and squaring those digits and then summing them together and the other thing that we need to do is we need to define a data structure that's going to be responsible for holding the numbers that we've seen already so that as we go through our loop we can check against this data structure to find out if we're stuck in an endless loop so let's look at how we can accomplish the first thing breaking the number down and squaring its digits and summing them together so let's say that we get the number 19 as our input and by the way i'm here in the chrome developer tools console just so we can look at this example so given the number 19 what we want to do is we want to first get the number in the ones place so we're going to get the 9 and we want to square that once we square it we can store it in a variable that will act sort of as an accumulator so after we've squared this number and stored it we're going to break down our number to get rid of this 9 which will leave us with the 1 in this case which will then square and add to that accumulator variable and we're going to be doing this process in a loop so this process is going to continue and that loop will check if our number has reached zero yet because each time that we go through this process and we continue to break down the number our number is eventually going to reach zero right because we'll have no digits left so in order to get the square of the number in the ones place this 9 for example we're going to use the modulo operator the modulo operator which is also sometimes called the remainder operator works like this let's say we take our num which right now is 19 and we use the modulo operator which looks like this so we do num modulo 10 as you can see this is going to give us this number the number nine because the way that the modulo operator works here in this example is we take the number 19 we divide it by 10 and then we see what the remainder is so since 19 can only be divided by 10 once we're left with a remainder of 9. let's look at the number 18. let's do 18 modulo 10 and we can see again we get the number 8 because after we've divided 18 by 10 we're left with a remainder of 8. and this will work with whatever number we give it so let's say we randomly just put this number in we do modulo 10 you can see we're left with the seven and then as i said we also need to be breaking this number down as we loop so once we've used the modulo operator to square the number in the ones place we're then going to want to take the number like so in divided by 10 but since we're using javascript we're going to need to use math.floor in order to get the number that we want so in our loop we would use math.floor divide the number by 10 which would leave us with 1 and then the next time around our loop we would use the modulo operator again on the 1 and then square it and then we can add that result to that accumulator variable that we've been working with so that's the process that we're going to use for working with the numbers and getting the various sums that we need now let's take a look at the data structure that we're going to use to keep track of the sums that we've seen already so as we're going around our loop we could choose to store sums in the form of an array but for this problem since we're simply going to be using this data structure to check to see if we've seen our sum already a better choice would be to use a set because the thing about a set in contrast to an array is that in a set a value can only occur once so we can't have duplicates of values in our set and the way that we can create a set in javascript is like this we can say for example let previously seen sums equal a new set and now that we have our set we can add values to it for example like this previously seen sums we can use the add method and let's say we put in five so now we can see that our set has one value it has the number five let's put another number in there let's say we put in the number six so now we have two values of five and a six but let's say that we tried to add the number five again well as you can see that number five it doesn't get added again because we already have the number five in the set so the size of the set remains at 2 and we still only have a 5 and a 6. as we're going through our loop we can check for the existence of one of these values in our set by using another method which sets have and that method is called has so we can say previously seen sums dot has let's say five and that returns us true because five is in the set if we were to say dot has seven of course we get false so let's go into vs code now and let's implement our algorithm here in vs code let's go ahead and let's set up our function we'll define a function called happy number and it's going to take a number which we'll call n and so now we know that we're going to want to set which is going to be used to store all the sums that we see so let's go ahead and set that up we'll say const let's call it previously seen sums and we'll set that to equal a new set now we want to start our loop and we're going to set this up as a while loop and it's going to loop while n does not equal 1. so initially n is going to be the number that's passed in as an argument but as you're going to see in a second as this while loop is continuing on we're going to be updating the value of n so we're going to be looking for it to at some point either equal 1 which would mean it's a happy number and we can return true or another thing that we're going to be doing in this loop is that we're going to be checking against our set the previously seen sums to see if we've seen the sum already in which case we're going to return false because we'll know that the number is not happy and that we're in an endless loop so in this loop let's set up a variable which we'll call current sum and we'll initialize this to a value of zero and now is when we're going to go through that process where we get each number in the ones place we square that number and we add it to our accumulator which is going to be this current sum and then we continuously break down that number until it's no longer greater than zero which point we're going to break out of this process so we're going to do it like this we're going to set up another while loop and we're going to say while n is greater than 0 this is where we want to go through this process where we're going to take our accumulator so current sum and we'll say current sum plus equals and here's where we're going to use that modulo operator so we're going to do n modulo 10 and we want to square it so we can say times and modulo 10. and then to break the number down we're going to set n to equal math.floor and divided by 10. so until the input number n is fully broken down we're going to be taking the number in the ones place we're going to be squaring it and we're going to be adding it to our accumulator and then this line here is going to be used to break it down essentially and assign that new value to n and this is all going to loop until this process is finished now once we've gotten the new sum which is stored as current sum the next thing to do is check to see if we've seen that number before so let's write an if statement and we're going to look at that previously seen sums set we're going to use the has method passing in that new current sum and we use the bang operator here so we're saying if that set doesn't have the current sum so if we haven't seen it before then what we want to do is we want to add it to the set and now we're going to set n to be that new current sum so at this point we haven't seen the sum yet and we know that n isn't equal to one yet because if it was we wouldn't be in this while loop but now the thing is if we have seen this number already in the set we can use an else statement and we can return false because if that number isn't a set that means we're in an endless loop and we don't have a happy number but in the case where we met this first condition if n is not yet equal to 1 we're going to be going around again in this loop we're going to continue in this while loop and we'll continue with this process of breaking down the number creating a new current sum checking to see if it's in the set and now finally if current sum at some point does equal 1 well n will get set to that value of 1 and at that point we're going to break out of our loop right because the condition is that n doesn't equal 1. so since at that point we know that we've gotten to the number 1 we know we have a happy number and we can return true all right so let's go ahead and let's try out this algorithm so we'll log out to the console happy number and let's pass in 19 and we know that 19 should return true because it is a happy number so let's save and here we go we see we got true here in the console let's pass in 18 which we know is not a happy number so this should return false and let's save and here we see false alright so why don't we give it the ultimate test let's copy our code and let's go into lead code and paste it in and we don't need this line here and let's run the code and here we can see it's been accepted and now let's submit it and here we can see success so thanks for checking out this video on the lead code problem called happy number if you enjoyed the video please give it a like consider subscribing to the channel and i'll see you next time

Channel: The Code Creative

Views: 1,108

Rating: 5 out of 5

Keywords: leetcode, leetcode happy number, leetcode happynumber, leet code happy number, leetcode 202, 202 leetcode happy number, how to solve leetcode happy number, how to solve happy number, leetcode javascript, happy number javascript, leetcode solutions, help with leetcode problems, leetcode problems happy number, google interview questions, google happy number, cracking the coding interview, coding interview preparation, the code creative, code creative, gregg fine

Id: vIQY1k0vyGo

Length: 13min 26sec (806 seconds)

Published: Tue Aug 11 2020