Happy Number Algorithm

A good excuse to use recursion beyond the Fibonacci series and factorials

Most of the programming students had heard about recursion. In most cases after a brief explanation, the instructor always shows an example of the use of recursion calculating the Fibonacci series or the factorial of a number.

After that, the teacher says… ok now you know what recursion is and you can use it whenever you have a repetitive task…

Well, we all know that’s not accurate. Don’t get me wrong, I know the Fibonacci series and Factorial are the easiest algorithms to try to explain what recursion means. But like everything in life, understanding and applying recursion requires practice. So let’s take advantage of this simple algorithm and put those concepts into practice

Let’s take a look to the task:

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process:

a) Starting with any positive integer.

b) Replace the number by the sum of the squares of its digits,

c) Repeat the process until the number equals 1

Those numbers for which this process ends in 1 are happy numbers.

Example:

Input: 19
Output: true
Explanation: 
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

As you can see, this task requires a series of repetitive steps that can be done using a recursive algorithm.

Disclaimer: ‘It’s evident that this task may be solved in a plethora of different ways, but as I said our purpose is to practice recursion”. So let’s do it.

The solution proposed

const isHappy = (number) => {
  const digitsOfTheNumber =(number, array=[])=>{
     if (number>=1){
        array.push(number%10)
        number = Math.floor(number/10)
        return digitsOfTheNumber(number, array)
     } else{
      return array
     }
   }
const answer = digitsOfTheNumber(number).reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
return answer === 1 ? true : answer === 4 ? false : isHappy(answer)
}

I know, I know… I almost can hear people yelling at me: “that’s not good code”… “it’s not clear”… “why use that ternary operator in that way, that is just not right”. My apologies. I just want to show to new coders things that they might found when they read code from others. It’s better to know it and don’t need it than need it and not know it, right?

Now that you ‘ve seen the answer you can go and push that submit button in leetcode, if that was all that you were interested in. After that come back and try to understand why this works.

Analyzing the problem

What is the first thing we need to solve when we read this problem? If you don’t know try to figure it out.

Ok, the answer is… get the digits of the number. Now, how can we do that?

We can split a number using two very rare math operators / and % (division and module), that’s right, it’s all that we need. So, in order to obtain each digit, we’re are going to get the module and the division of the number till the number become less than one.

Example:

N = 19
First Step
19 % 10 --> 9
19 / 10 --> 1.9 --> here we just need to round down --> 1
Repeat the process with result
1 % 10 --> 1
1 / 10 --> 0.1 Stop
Another example
N=123
First step 
  123 % 10 --> 3
  123 / 10 --> 12.3 round down --> 12
Second Step
  12 % 10 --> 2
  12 / 10 --> 1.2 round down --> 1
Third Step
  1 % 10 --> 1
  1 / 10 --> 0.1 Stop
We got the digits

*why module 10 and divided in 10? because are base 10 numbers.

Now, let’s take a look to our solution and look when and how this is happening.

Firs we declare our main function
const isHappy = (number) => { 
Now, here we have another function 
|  const digitsOfTheNumber =(number, array=[])=>{
|     if (number>=1){
|        array.push(number%10) --> look familiar?
|        number = Math.floor(number/10) --> look familiar?
|        return digitsOfTheNumber(number, array)
|     } else{
|      return array
|    }
|   } 
|_____
const answer = digitsOfTheNumber(number).reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
return answer === 1 ? true : answer === 4 ? false : isHappy(answer)
}

Let’s isolate this function and let’s analyze it.

const digitsOfTheNumber = (number, array=[])=> {

We declare a function with two arguments number and array. **Remember the name of the function**. Here is clear that “number” is the value that we’re going to separate but what about “array”? As you may have noticed we need to keep the digits in order to operate them, and an easy way is to put them into an array.

if (number>=1) {

Now we declare our stop condition… ok ok our “go condition”. As we saw in the previews examples we need to repeat the module and division process until our number becomes 1 or less.

array.push(number%10)

Here we push the first digit into our array.

number = Math.floor(number/10)

Now, we use the Math.floor function to round down our division, getting the next number that we need to process.

return digitsOfTheNumber(number, array)

Now, take a look at this. Here’s when the magic happens. Instead of using an iterative structure, we’re are returning and calling the same function. What that means is that this process is done over and over again. That’s recursion!!

Let’s examine carefully what are the values that we’re passing to this function.

We’re passing number and array. But now array has the first value that we pushed the first time we run the function, and number is the result of round down the division of the number. The arguments continually change, each time we call the function.

else {
return array
}

Once the number is less than 1 the function returns the array and stops its execution. Now we have all the digits separated into an array in the “digitsOfTheNumber” constant.

How are you doing so far? time for a break? Just stretch and let’s continue.

Now it’s time to analyze the second part of the problem. Once we have the digits we need to “sum the squares of each digit”. So, let’s take a look at how we’re doing that.

What do we have here?

const answer = digitsOfTheNumber(number).reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
return answer === 1 ? true : answer === 4 ? false : isHappy(answer)

Let’s see. We have a new variable called answer. That variable has something called “digitsOfTheNumber” “reduce”. Wait a minute, we just saw that digitsOfTheNumber was the function that gave us the digits, and that function returns an array. That means that now we’re operating with an array and that reduce function make sense.

Let’s make sure we’re getting what’s happening here.

Here's our main function
const isHappy = (number->🙋🏻) => {
The first thing this function does is to declare a constant called answer that calls the digitsOfTheNumber function passing the argument "number->🙋🏻"
const answer = digitsOfTheNumber(number->🙋🏻).reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
return answer === 1 ? true : answer === 4 ? false : isHappy(answer)
}

Once digitsOfTheNumber is called the number is operated into that function and the result is an array with the digits of that number.

|  const digitsOfTheNumber =(number->🙋🏻, array=[])=>{
|     if (🙋🏻>=1){
|        array.push(🙋🏻%10)-> now array has a digit [🙋🏻]
|        number = Math.floor(🙋🏻/10) each pass is a new number->🙋🏽
|        return digitsOfTheNumber(🙋🏽, [🙋🏻])
|     } else{
|      return array -->[🙋🏻,🙋🏽]
|    }
|   } 

Now we have an array that we operate using the reduce function.

const answer = digitsOfTheNumber(number).reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
  
*** [🙋🏻,🙋🏽].reduce

What reduce function does is sum the squares of each digit in the array and give us the new number.

[1,9].reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
first time
accumulator  --> 0
currentValue --> 1 --> 1**2 -> 1 
second time
accumulator --> 1
currentValue --> 9 --> 9**2 ->81
return 1+81 --> 82

I hope that’s clear enough.

Let’s see the last part of the function. If you’re unfamiliar with the ternary operator, this might look weird. But it’s actually quite easy.

return answer === 1 ? true : answer === 4 ? false : isHappy(answer)

Here’s a definition what the ternary operator is:

“The ternary operator is an operator that takes three arguments. The first argument is a comparison argument, the second is the result upon a true comparison, and the third is the result upon a false comparison”.(source)

Let’s break down this ternary operator :

return answer === 1 ? true : answer === 4 ? false : isHappy(answer)
"Is answer equal 1?"   [answer === 1] [?] 
"yes" *return*         [true] 
"no"                   [:]
"Is answer equal 4?"   [answer === 4] [?]
"yes" *return*         [false]
"no"                   [:] 
return                 [isHappy(answer)]

Of course, we can replace this for a common if-else statement.

if(answer === 1){
 return true
} else if (answer===4){
 return false
} else {
 return isHappy(answer)
}

Now, what did you see here?

In the last return we’re returning the same function with the new answer value. And YES we are using recursion once again.

Let’s try to make a whole example here:

isHappy(19)
Step 1 
const answer =digitsOfTheNumber(19)...Now we call that function
Step 1.1.1
digitsOfTheNumber(19)
|  const digitsOfTheNumber = (19, array=[])=>{
|     if (19>=1){-->YES
|        array.push(19%10)          array --> [9]
|        number = Math.floor(19/10) number --> 1
|        return digitsOfTheNumber(1, [9])
Step 1.1.2
|  const digitsOfTheNumber = (1,[9])=>{
|     if (1>=1){-->YES
|        array.push(1%10)            array --> [9,1]
|        number = Math.floor(1/10)  number-> 0
|        return digitsOfTheNumber(0, [9,1])
Step 1.1.3
|  const digitsOfTheNumber = (0,[9,1])=>{
|     if (0>=1){-->NO
|        ---           
|        ---}
|     --> else{
|      return array -->[9,1]
Step 1.2 
[9,1].reduce((accumulator, currentValue) => accumulator +(currentValue**2),0)
Step 1.2.1
accumulator  --> 0
currentValue --> 9 --> 9**2 -> 81 
Step 1.2.2
accumulator --> 81
currentValue --> 1 --> 1**2 ->1
return 81+1 --> 82
 
Now answer is 82
Step 1.3
return 82 === 1 ? true : 82 === 4 ? false : [isHappy(82)]-->true
"Is 82 equal 1?"       [82 === 1] [?] --> No
"yes" *return*         [true] -->discard
"no"                   [:]
"Is answer equal 4?"   [answer === 4] [?]--> No
"yes" *return*         [false]-->discard
"no"                   [:] 
return                 [isHappy(answer)] --> Winner
Step 2
isHappy(82) -->star over

Well, that’s it. I hope you’ve enjoyed this article and now try to apply recursion to another problem.

Keep coding!