Solving LeetCode 258 Add Digits Problem in JavaScript Step-by-Step

Applying separation of concerns concepts and backtrack recursion

After bootcamp graduation I spent a lot of time learning CS fundamentals, data structures and algorithms. And while I have seen and solved problems using recursion before (hello binary search tree traversals!) this was the first time I encountered a problem where immediately I thought: while loop or recursion. But recursion is where I need most practice, so let’s do that!

The problem states that we’re going to be given a number, say 38. Our goal is take this number apart (3 || 8), add the digits (3 + 8 = 11), and to keep doing this until our number is a single digit, and then return it. At this point we’d need to do it one more time: 1 + 1 = 2. Since 2 is a single digit, we’d stop, and return 2.

Finding an algorithm

I find the best way to solve these problems is to do it by hand (like we did above), and then pseudocode, then actual code. The pseudocode for my approach is:

• Grab the number, split it up
• Sum its parts. If that number is one digit, return it.
• If it’s not one digit, start over, and do it again.

When I wrote it down like this, recursion jumped out.

Coding up a solution

Let’s get this out of the way first.

There is a one-line solution to this problem. But frankly, unless you saw it before, or had significant experience with mathematics algorithms, it’s unlikely you’d figure it out:

function addDigits(num) return (!num) ? 0 : (num % 9 || 9)};

There’s a lot going on here, and I’m not going to bother deconstructing it because, besides the concept of ternaries and modulus operators, I don’t find this to be very useful to the typical student of the engineering / coding craft. It’s just another, “you’ve either seen it, or you haven’t”. Now you have. Let’s move on.

Referring back to our algorithm, we know we have to split the number up somehow in order to add it. Here’s the thing, though: because it’s not an iterable, you can’t split up an integer in JavaScript. So first, let’s turn it into a string. And then, let’s take that result and split it up:

num.toString().split("");

That will take our 38, and make it [“3”, “8”]

Now we need to take each element of this array, and sum its parts. But because its a string, we need to turn it back to an integer before trying to add it. Here’s one way to do that:

arr.reduce((a, b) => parseInt(a) + parseInt(b), 0);

Reduce is a pretty nifty method to have in your back pocket. It allows you to execute a callback (here, adding) for each element of a provided array, starting at index 0.

This takes our [“3”, “8”] array and returns 11.

But since our number still has more than 2 digits, we need to do this all over again. And this is where the recursion would take place.

For simplicity’s sake, and to practice the design pattern of separation of concerns, I chose to make small functions to handle each one of the above steps.

Below is the full code:

(1) function addDigits(num) {
(2)  let numSplitRet = numSplit(num);
(3)  let numSplitSumRet = numSplitSum(numSplitRet);
// base case:
(4)  if (numSplitSumRet < 10) return numSplitSumRet;
// recursive case
(5)  function numSplit(num) {
(6)    return num.toString().split("");
(7)  }
(8) function numSplitSum(arr) {
(9)    return arr.reduce((a, b) => parseInt(a) + parseInt(b), 0);
(10)  }
(11)  return addDigits(numSplitSumRet);
(12) }

Code walk through

• First step, in line 2, we split our number so we can iterate through it. So we call the numSplit function (line 5) with our number (38). As explained above, this will return [“3”, “8”], and house it in numSplitRet.
• Next, we’ll call another function (numSplitRet in line 8), with our array of [“3”, “8”]. As explained above, this will return 11, and house it in numSplitSumRet.
• Now we test if we’re done. This is what a base case does in recursion. It’s the part of a recursive function that lets it known if it’s done, and doesn’t need to keep calling itself. And without it, an infinite loop or stack overflow, will likely occur. Our base case asks, “is our number one digit?”. A simple way to test this if our number is less than 10. We can assume this because our problem stated that we’ll always get a positive integer. And all positive integers that are less than 10 have a single digit. But 11 > 10, so this (line 4) evaluates to false.
• The code then goes to line 11, and calls addDigits again. But this time, instead of an input of 38 like we had first, it’s called with 11.
• So, like in our first step, we call the numSplit function, and save [“1”,”1”] in numSplitRet.
• We then call numSplitSum with the [“1”,”1”] array which will return 2 and save it in numSplitSumRet.
• Next the conditional asks if 2 is less than 10. It is! So we return this to our previous calls, and ultimately exit out of the function.

Thanks for reading!

And remember…

Grit > talent.