Solving Popular Algorithms: Add Strings
I’m not going to lie: I clicked on this problem because I thought it would be easy. I mean, it’s just adding strings right? How hard could it be?
Well, much to my surprise and, honestly, irritation, this problem was actually kind of challenging as adding large numbers without BigInt seemed like a logistical nightmare. And it is.
But, logistical nightmares often make us better, more adaptable coders. So even if you, like me, look at this problem and have no desire to even attempt a solution, I promise it will be worth it in the end!
Thus, without further ado, let’s get right into solving Leet Code’s Add Strings .
The Problem
The goal of this problem is very simple. Given two strings of numbers, add them together.
Sounds easy, right?
Well unfortunately, the tests in this problem bar us from using any built-in BigInteger library or converting the inputs to integers directly.
This, unfortunately means, that we (mostly…) can’t rely on useful and commonplace addition methods such as parseInt or BigInt. Instead, we will have to figure out our own way to add these two strings of numbers.
The Solution: An Overview
Now, I should clarify, we can and will use parseInt in our solution to this problem. Unfortunately, however, we can’t use BigInt at all meaning that any large number, of which there are many in our test cases, will not be able to be added correctly via parseInt. Thus, we have to figure out a solution to our problem that does not rely on either parseInt or BigInt.
Basically, in order to solve this problem, we will have to return to elementary school adding strategies:
Our strategy for this problem will pretty much be like the picture above. We will line up our two numbers, end-to-end. Then, we will go backwards down the line and add up the two vertical numbers. If the sum of these numbers is greater than 10, we will “carry the one” over to the numbers in front and add it to the next sum.
Following this basic strategy, we will be able to add any two numbers together regardless of how big they are!
The Solution: Lining Up Our Numbers
One major issue I had with this problem when I first started was how to line up two numbers that were of different lengths. Since we need to add starting from the ends, getting the numbers correctly aligned was of huge importance.
After trying a bunch of different options such as for loops and while loops and *shudder* nested for loops, ultimately, I realized that the best solution to this issue was to just make the numbers the same length.
To do so, I figured out which number was longer and by how many digits said number was longer, then I added that many zeros to the front of the shorter number. Thus, both numbers would be the same length, but our addition would not be affected.
*Also, I should quickly note that I split both of my strings into arrays. I do not think this step is completely necessary, I just am personally more comfortable iterating through arrays!*
let arr1 = num1.split("")
let arr2 = num2.split("")let numZs = 0
if (num1.length > num2.length) {
numZs = num1.length - num2.length
while (numZs > 0) {
arr2.unshift("0")
numZs--
}
} else {
numZs = num2.length - num1.length
while (numZs > 0) {
arr1.unshift("0")
numZs--
}
}
**We will be using the JS method unshift a lot in this problem. It is basically the opposite of the push method as it allows to add elements to the front of an array, instead of the**
The Solution: Elementary School Addition
Now that we have figured out how to line up our numbers, we can move right on to our elementary school addition strategy.
I’m going to assume you remember how to add in this manner and just get right into showing you my code. I should note, however, while this code does look complex, the strategy behind it is quite simple and I will go over it in more depth below to make sure we are all on the same page!
let results = []
let secondDig = 0for (let i = arr1.length-1; i >= 0; i--) {
let sumNum = parseInt(arr1[i]) + parseInt(arr2[i]) if (sumNum >= 10) {
arr1[i-1] = (parseInt(arr1[i-1]) + 1).toString()
let gettingSecondDig = sumNum.toString().split("")
secondDig = gettingSecondDig[1] if (i === 0) {
results.unshift(sumNum.toString())
} else {
results.unshift(secondDig)
}
} else {
results.unshift(sumNum.toString())
}}
Since, both of our numbers are now the same length, we can use either array length to set our i value, which will be set to the length of either array minus 1 (remember arrays start at index 0!) because we are going to start adding from the end.
Here, is where we will make use of our parseInt function. Remember, if we were to add the string “9” and “7” together we would get “97”. If we were to parseInt our strings, however, we would get the correct sum of 16.
Then, you’ll notice our if statement. Thinking back to elementary, we know that if two sums are greater than or equal to ten, we will need to carry the one and leave only the second digit of the sum in our final sum. This if statement is where we accomplish that task.
So, if our sum of the two vertically aligned numbers is greater then 10, then we have to do two things. First, we need to add a 1 to the upcoming vertical sum. We can do this by accessing arr[i-1] (remember we are moving backwards, so this will be our upcoming number) and adding one to the parseInt of that value. Then, in order to avoid complications, I reconverted that value back to a string.
Second, we need to make sure we are only adding the second digit our sum to our final results array. To do that, we convert our sum to a string, split the string, and then grab the second number in our newly made array. Then, we can add this number to our final results array.
There is, however, one exception to this part of our plan and that is if we are working with our final set of numbers. If i = 0, then we know that we are at our first numbers and thus whatever our sum is, even if it’s over 10, we want to directly add it to our results array.
To complete this part of the problem, we complete our if statement by just simply adding a string version of any sum to results that is less than 10, as for a number smaller than 10 we do not have to worry about carrying the one.
The Solution: The Finale
Now, that we understand how the two main parts of our solution work, here is our final algorithm:
addStrings = (num1, num2) => {
let arr1 = num1.split("")
let arr2 = num2.split("") let numZs = 0
if (num1.length > num2.length) {
numZs = num1.length - num2.length
while (numZs > 0) {
arr2.unshift("0")
numZs--
}
} else {
numZs = num2.length - num1.length
while (numZs > 0) {
arr1.unshift("0")
numZs--
}
}
let results = []
let secondDig = 0 for (let i = arr1.length-1; i >= 0; i--) {
let sumNum = parseInt(arr1[i]) + parseInt(arr2[i]) if (sumNum >= 10) {
arr1[i-1] = (parseInt(arr1[i-1]) + 1).toString()
let gettingSecondDig = sumNum.toString().split("")
secondDig = gettingSecondDig[1] if (i === 0) {
results.unshift(sumNum.toString())
} else {
results.unshift(secondDig)
}
} else {
results.unshift(sumNum.toString())
} }
return results.join("")
}
Before we go, remember that our problem wants a string to be our final output, thus join the results array in your return statement!
And with that, our foray back into elementary school is complete and we can pat ourselves on the back for another problem solved!
As always, please try this problem on your own and good luck and happy coding!
