Add Strings

Good day! My wife and I had a good weekend. Hopefully you did also.

As I was generating this post I noticed that my blog has passed the 5,000 subscribers!!! Thanks to all of you. If you have suggestions on how to improve, I would be interested in learning your thoughts. Once again; thanks to all of you.

Over the weekend my wife and I prepared Oxtail Stew. It was very yummy! We coated the oxtail parts with some olive oil. On a baking tray we placed the pieces. We put them in an oven at 550F. As soon as the pieces started to get cooked, we flipped them and put them back in the oven to repeat the process. We were looking for nice color all around.

While in the oven we chopped onions, celery and some carrots to make our mirepoix. We did not add oil, salt, pepper or any other condiments.

We took the oxtail, the mirepoix and a couple cups of chicken broth and put them in an electric pressure cooker for 90 minutes. Oxtail contains a lot of fat , which like many other things in life, it is good with moderation, so it is better to let it melt away and when done, remove most of it.

When the timer expired, we moved the contents int a Dutch oven and added two small cans of tomato paste. At that point we seasoned the mix with some salt and pepper. We cover the Dutch oven and let it simmer on low for an hour or so.

For lunch we served the stew over a bed or rice. We put some cooked rice on a pan with some olive oil and let it get somewhat crunchy at medium heat. It takes about 10 to 15 minutes to get really yummy.

My wife does not like spicy food; but I do. After serving my dish (OK I had two servings) I put some Trader Joe’s Green Hot Sauce. Probably one of the best oxtail stews I have eaten so far. By the way, while looking for the hot sauce on line, I found out  that you could get it at Amazon.

Let’s get down to the main subject of this post. Earlier today I decided to give a try to LeetCode 415 Add Strings problem.

Given two non-negative integers num1 and num2 represented as string, 
return the sum of num1 and num2.

Note:

o The length of both num1 and num2 is < 5100.
o Both num1 and num2 contains only digits 0-9.
o Both num1 and num2 does not contain any leading zero.
o You must not use any built-in BigInteger library or convert the inputs to integer directly.

If you are interested please visit the LeetCode site and get the requirements directly from the horse’s mouth.

The requirements for the problem are to perform the addition of two strings with positive numbers. Like I said, most of us perform some type of addition on a piece of paper at least once a day. Now this is our opportunity to add the numbers without using a calculator.

Make sure you read the last note on the requirements. We cannot convert the strings to binary, add them, convert the result back to a string and return it as an answer.

public String addStrings(String num1, String num2) {

}

The signature for the function / method in Java is simple. It takes two positive integers. This can be deduced because the strings do not contain any other symbol but digits [0 : 9].

123
456
main <<< str1 ==>123<==
main <<< str2 ==>456<==
<<< len: 3
<<< len: 4
<<< num1 ==>123<==
<<< num2 ==>456<==
<<< i: 2 sum: 9 carry: 0
<<< i: 1 sum: 7 carry: 0
<<< i: 0 sum: 5 carry: 0
<<< res: [5, 7, 9, ]
main <<< result: 579
<<< i: 2 j: 2 sum: 9 carry: 0
<<< i: 1 j: 1 sum: 7 carry: 0
<<< i: 0 j: 0 sum: 5 carry: 0
main <<< result: 579


12
345
main <<< str1 ==>12<==
main <<< str2 ==>345<==
<<< len: 3
<<< len: 4
<<< num1 ==>012<==
<<< num2 ==>345<==
<<< i: 2 sum: 7 carry: 0
<<< i: 1 sum: 5 carry: 0
<<< i: 0 sum: 3 carry: 0
<<< res: [3, 5, 7, ]
main <<< result: 357
<<< i: 1 j: 2 sum: 7 carry: 0
<<< i: 0 j: 1 sum: 5 carry: 0
<<< i: -1 j: 0 sum: 3 carry: 0
main <<< result: 357


9999
9999
main <<< str1 ==>9999<==
main <<< str2 ==>9999<==
<<< len: 4
<<< len: 5
<<< num1 ==>9999<==
<<< num2 ==>9999<==
<<< i: 3 sum: 18 carry: 1
<<< i: 2 sum: 19 carry: 1
<<< i: 1 sum: 19 carry: 1
<<< i: 0 sum: 19 carry: 1
<<< res: [9, 9, 9, 8, ]
main <<< result: 19998
<<< i: 3 j: 3 sum: 18 carry: 1
<<< i: 2 j: 2 sum: 19 carry: 1
<<< i: 1 j: 1 sum: 19 carry: 1
<<< i: 0 j: 0 sum: 19 carry: 1
main <<< result: 19998


987
99999
main <<< str1 ==>987<==
main <<< str2 ==>99999<==
<<< len: 5
<<< len: 6
<<< num1 ==>00987<==
<<< num2 ==>99999<==
<<< i: 4 sum: 16 carry: 1
<<< i: 3 sum: 18 carry: 1
<<< i: 2 sum: 19 carry: 1
<<< i: 1 sum: 10 carry: 1
<<< i: 0 sum: 10 carry: 1
<<< res: [0, 0, 9, 8, 6, ]
main <<< result: 100986
<<< i: 2 j: 4 sum: 16 carry: 1
<<< i: 1 j: 3 sum: 18 carry: 1
<<< i: 0 j: 2 sum: 19 carry: 1
<<< i: -1 j: 1 sum: 10 carry: 1
<<< i: -2 j: 0 sum: 10 carry: 1
main <<< result: 100986


0
0
main <<< str1 ==>0<==
main <<< str2 ==>0<==
main <<< result: 0
main <<< result: 0


1
1
main <<< str1 ==>1<==
main <<< str2 ==>1<==
<<< len: 1
<<< len: 2
<<< num1 ==>1<==
<<< num2 ==>1<==
<<< i: 0 sum: 2 carry: 0
<<< res: [2, ]
main <<< result: 2
<<< i: 0 j: 0 sum: 2 carry: 0
main <<< result: 2


408
5
main <<< str1 ==>408<==
main <<< str2 ==>5<==
<<< len: 3
<<< len: 4
<<< num1 ==>408<==
<<< num2 ==>005<==
<<< i: 2 sum: 13 carry: 1
<<< i: 1 sum: 1 carry: 0
<<< i: 0 sum: 4 carry: 0
<<< res: [4, 1, 3, ]
main <<< result: 413
<<< i: 2 j: 0 sum: 13 carry: 1
<<< i: 1 j: -1 sum: 1 carry: 0
<<< i: 0 j: -2 sum: 4 carry: 0
main <<< result: 413

The problem does not provide examples. I guess we do not need an example on how to add numbers. That said; our code needs to address end conditions. As we will see, there are a few conditions that we should take care of, based on how we approach the problem.

As you know, I like to develop code on my computers. I will develop this code using Java on a Windows 10 machine using the VSCode IDE.

Since I am developing the solution on my computer, I will require a test scaffolding to collect the strings, pass them to the call we need to implement, and finally display the results.

As we can see we are provided with two numbers. We appear to read and display them to make sure all is well so far.

We then start processing. This seems to be happening in the addStrings() function. After a few lines out debugging output we see the result. Mentally we can verify that it is correct.

It seems that we have a second implementation. It too displays some debug statements. Finally the result of the operations is displayed. The results seem to match in all examples. More important, the results seem to be correct.

    /**
     * Test scaffolding
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read both strings ****
        String str1 = br.readLine().trim();
        String str2 = br.readLine().trim();

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< str1 ==>" + str1 + "<==");
        System.out.println("main <<< str2 ==>" + str2 + "<==");

        // **** compute and display result ****
        System.out.println("main <<< result: " + addStrings(str1, str2));

        // **** compute and display result ****
        System.out.println("main <<< result: " + addStrings1(str1, str2));
    }

This is our test scaffolding. Note that IT IS NOT PART OF THE SOLUTION. I need one because I am developing the code on my machine. When done, I will just copy and paste it to the LeetCode site. I will make sure to remove all debugging statements and then give it a try.

We read the two input lines. We display them to make sure all is well so far. We then call two versions of the function and display results. I guess this makes sense based on the output we previously saw for the different test cases.

    /**
     * Processing two character arrays.
     * 
     * Runtime: 3 ms, faster than 37.61% of Java online submissions.
     * Memory Usage: 39.3 MB, less than 26.61% of Java online submissions.
     */
    static String addStrings(String num1, String num2) {

        // **** sanity check(s) ****
        if (num1.equals("") || num1.equals("0")) {
            return num2;
        }

        if (num2 == "" || num2 == "0") {
            return num1;
        }

        // **** get length of largest string ****
        int len = Math.max(num1.length(), num2.length());

        // ???? ????
        System.out.println("<<< len: " + len);

        // **** take into account possible carry over ****
        len++;

        // ???? ????
        System.out.println("<<< len: " + len);

        // **** prepend '0' to the shortest string ****
        if (num1.length() > num2.length()) {
            while (num1.length() != num2.length())
                num2 = "0" + num2;
        } else if (num1.length() < num2.length()) {
            while (num1.length() != num2.length())
                num1 = "0" + num1;
        }

        // ???? ????
        System.out.println("<<< num1 ==>" + num1 + "<==");
        System.out.println("<<< num2 ==>" + num2 + "<==");

        // **** initialization ****
        char[] arr1 = num1.toCharArray();
        char[] arr2 = num2.toCharArray();
        char[] res  = new char[len];
        int carry   = 0;

        // **** loop from right to left ****
        for (int i = len - 2; i >= 0; i--) {

            // **** compute sum of digits with same position ****
            int sum = carry;
            sum     += (arr1[i] - '0');
            sum     += (arr2[i] - '0');

            // **** update result array ****
            res[i] = (char)((sum % 10) + '0');

            // **** compute carry ****
            if (sum >= 10)
                carry = 1;
            else 
                carry = 0;

            // ???? ????
            System.out.println("<<< i: " + i + " sum: " + sum + " carry: " + carry);
        }

        // ???? ????
        System.out.println("<<< res: " + Arrays.toString(res));

        // **** ****
        StringBuilder sb = new StringBuilder();

        // **** ****
        if (carry != 0)
            sb.append(String.valueOf(carry));

        // **** remove null character ****
        sb.append(res, 0, len - 1);

        // **** return result as a string ****
        return sb.toString();
    }

In this case I decided to use two character arrays. The solution executed in a decent time. Let’s look at the code and then come up with hopefully a simpler implementation with the same approach. As far as I know, most (never say all) of use add two numbers using the same technique. As usual, we can take care of some sanity checks. They tend to return an answer immediately with very little overhead. Most people do not include sanity checks in their code. I tend to do so. My first thoughts were to have the two strings the same length so we can traverse them with a single index. If this approach gets too cumbersome, we can make changes which we will see in the second implementation. We prepend 0’s to the shorter string (if any). Now we can use a single index. We display the strings to make sure all is well so far. We now enter the main loop. We will traverse the strings from right to left following what we do with a pen and paper. We add the carry, the first digit at the current position and the other digit in the second string at the same position. We update the result by noting the digit that will go into our answer. We then compute the carry. After we are done processing all the digits, we need to take into account the existence of a carry bit. I have to say that LeetCode was somewhat more stringent than what I initially coded. I would get the results to display currently but looking closer I was skipping null values in the res array. I made the necessary changes and the code was accepted. It seems that we had to deal with details prepending and then removing 0s. Let’s eliminate the 0s.

    /**
     * Without the two character arrays.
     * We can avoid prepending '0's to shorter string.
     * 
     * Runtime: 2 ms, faster than 91.94% of Java online submissions.
     * Memory Usage: 39.1 MB, less than 60.40% of Java online submissions.
     */
    static String addStrings1(String num1, String num2) {

        // **** sanity check(s) ****
        if (num1.equals("") || num1.equals("0")) {
            return num2;
        }

        if (num2 == "" || num2 == "0") {
            return num1;
        }

        // **** initialization ****
        int i               = num1.length() - 1;
        int j               = num2.length() - 1;
        int carry           = 0;
        StringBuilder sb    = new StringBuilder();

        // **** traverse strings right to left ****
        while (i >= 0 || j >= 0) {

            // **** sum associated digits with carry ****
            int sum = carry;
            if (i >= 0)
                sum += num1.charAt(i) - '0';
            if (j >= 0)
                sum += num2.charAt(j) - '0';

            // **** compute carry ****
            if (sum >= 10)
                carry = 1;
            else
                carry = 0;

            // ???? ????
            System.out.println("<<< i: " + i + " j: " + j + " sum: " + sum + " carry: " + carry);

            // **** append sum digit to string builder ****
            sb.append(sum % 10);

            // **** increment indices ****
            i--; j--;
        }

        // **** append carry (if needed) ****
        if (carry != 0)
            sb.append(carry);

        // **** return reversed string of digits ****
        return sb.reverse().toString();
    }

In this implementation we will use two indices, one for each string, which will eliminate the need for having the two strings with the same length.

We enter a loop that continues while one of the indices is greater than 0.

We perform the same operations as we did before to generate the sum and carry. Note that we pull one character at a time from the strings. If we ran out of digits on one of the strings we just pull the digit from the other.

We append the resulting digit to the string builder and increment both indices.

When we are done, we just need to take care of the carry bit.

Now we need to return the result string. Note that we generated it from right to left, but the result needs to be generated from left to right.

We used the same concept with a little more finesse.

Perhaps we could simplify things here and there, but at this point, it is past 06:00 PM and I had enough for one day.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all 5,028 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

Regards;

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.