HappyNumber - Crack Coding Interviews

Happy number. So a happy number is a number defined by the following process. Start with any positive integer, replace the number by the sum of the squares of its digits, and we're going to repeat the process until the number equals one. So apparently there could be a case where it will never equal to one, and you will end up looping. And if the number actually comes down to one after we keep applying this process, then that means the number is happy, otherwise it's not happy. So we're going to return a Boolean variable. If it's happy, then it's true. If it's false, otherwise, right? So let's take a look at one example. So if the input is equal to 19, so the very first thing you're going to do is take the first digit one, apply the square, plus the second digit square. So that's one square plus nine square is equal to 82, right? So we're going to then apply the same process, take 82, and then do a square plus two square, and that takes you to 68. So we keep doing the process until we eventually equal to one. And if that's the case, that means this input is true. That means it's a happy number, right? So how do we tackle this problem? Well, it seems like it's a pretty classic example where we have to repeat the same process over and over again, right? So it would be helpful if we have a helper function that can basically be very generic, and it would just take any integer and apply this process and return the sum of the squares, right? And so in order to do that, let's first code a helper function. So this function is going to be returning an integer. It's going to be the sum of the squares of all the digits, right? So let's just call this helper. Apparently, it's going to take an input. And notice that this one and this one are different. Actually, let's call it a different number. Let's call it integer t, right? So we're going to say first result is equal to zero, and eventually we want to return this result, right? So we want to keep applying the same process, right? So you notice that if we satisfy these conditions, the input n, right? So first is 82, then 68, then 100, and eventually equal to 1, right? So we're going to say while t is greater than zero, because if the theory is right, if it's actually a happy number, eventually it's going to come down to 1, right? So let's see. We can go backward, right? So if you take any input integer, say 82, right? So how do I get the last digits? So that's 82, sorry, 82 divided by 10, that's equal to 8, right? With the remainder of 2. So that's actually 82 mod 10. So you take the remainder and you divide 82, divide the number by 10, take the remainder, right? So we're going to say this last digit, d is equal to t mod 10, right? So this is going to take the last digit, and then you add this to the result. So I remember at this point, the result, if we keep doing the process, could already be holding some values, and the value will be the sum of the digits counting from right. So it should already have some value. So we're going to add, that's why we say add equals d times d squares, right? And then we're going to have to update t, and t is equal to divide equal to, so basically t is equal to t divided by 10, right? So all right, once we have this helper function, and we can think about this. So there could be two cases, and they already told us, right? So there could be two cases. Number one, you repeat the process until the number equals one. Secondly, it will loop endlessly in the cycle, right? So that has made the question a lot easier, because we only have to deal with these two scenarios. If it equals one, that means that's a happy path, and otherwise, it could loop endlessly in the cycle. And so for example, you apply AD2 with the process, and then takes you to 68. For example, let's assume that the 68 comes back to, you apply the process, it comes, AD2 becomes 68. Let's assume, let's assume that you apply the process, 68 becomes AD2. It'll just keep looping, right? So how do we detect these scenarios? You may think that, okay, so we may need a hash set, where we're storing the values already encountered. And that way, every time we apply the process, we can check if previously we have encountered this number before. If that's the case, then it's never going to reach the number one, right? So because if you encounter AD2 again, you will have to apply the same process that takes you to 68. It will just keep looping, right? So it will never take you to one. So first of all, first of all, we're going to define a hash set of integers. Let's just call it a set equals new hash set. And this is going to store all the values we have encountered in each step. So while n is greater than zero, right? So classically, we're going to say n is equal to helper of n, right? So, but we do have to add the check here for duplicates or for loops, right? So every time we're going to be adding set.add this to the set, every time we're adding the value. However, we need to check before we add or before we even update n, we need to check if we have already encountered this before. So if n is greater than zero, and the set contains, does not contain, so we're going to say contains n, and then we're going to negate this, right? So if the set doesn't contain n, then go ahead. Otherwise, we're going to return false. So eventually, what's going to happen is we're going to say return n is equal to one, whether n equals to one or not. So if the set contains n, it's not going to go into the while loop anymore. It will jump directly to line number eight and evaluate n, if n is equal to one or not, right? So let's run this. Okay. All right, there we go. So that's a pretty classic, and you may want to remember this helper method because it's a pretty classic example of how to get the sum of the squares. You can apply the same logic to a lot of problems.