[Solution]Problem 54:Multiply Strings[Google]

REEEEE

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

---

To my American Friends,

I hope you’re excited about Labor Day. I really need it. There is wayy too much I need to sort out. The old flatmates are moving out, and the new ones are coming in. Lots of housekeeping to be done. How will you be spending your weekends?

I hope you enjoyed this question that I shared yesterday.

This problem can be found as problem 43. Multiply Strings on Leetcode.

Problem

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Constraints:

• 1 <= num1.length, num2.length <= 200

• num1 and num2 consist of digits only.

• Both num1 and num2 do not contain any leading zero, except the number 0 itself.

You can test your solution here

Fun Fact: Some of you might be wondering why I picked this problem. I was talking to a professor that teaches Assembly Programming on Monday. He mentioned that people multiply large numbers as strings to prevent overflow (if the result goes over the space allocated to ints). In typed languages like Java, C, etc., this is especially critical.

How many Tech Newsletters would you call fun to read?

Step 1: Understanding what we’re going to do

This is one of those tricky brain-teasers. For problems like this, it can is important to take a step back and breathe. Look for areas you do understand. Find that low-hanging fruit and attack from there. It’s much better than sitting there in silence (or panicking).

Fortunately, the underlying problem we are tackling is multiplication. This is a process you should be intimately familiar with. By analyzing the multiplication process we should be able to figure out the next steps. I know that doesn’t immediately tackle the main part of the problem (no directly converting input to ints), but that will come later. Baby Steps first.

You get to the top by going one step at a time. Apply the same mentality here. Don’t rush your problem-solving process. Photo by Stephanie Cook on Unsplash

Step 2: Understanding Multiplication

This might seem silly, but how does multiplication work? Not how to multiply, but what is the process behind it? What is the theory behind multiplication? Let’s look into that now.

When we multiply 23 * 86, what are we actually doing? Not the process of multiplication, just what are we doing. We are actually doing the following sum-

23* 86 = (2* 10 + 3) * ( 8*10+ 6)   

Okay, but what does this do? Patience Paduan, patience.

This process of breaking down multiplication into individual steps can give us a possible shining path forward. If we can handle the individual multiplications, we can do the overall multiplication. This might sound a lot like Greedy Algorithms (which we discussed here). Is multiplication a Greedy Process? Think about that, and let me know what you think.

But how do we handle the individual multiplication, w/o converting the input into ints? Go character by character, convert individual chars into ints, and sum them up. This breaks the rule, we’ve been given. No directly converting into ints. Also, this process will force you to handle the carry-overs, which can be a messy process. So what can we do?

Break the rule. return int(num1)* int(num2) because you’re a sigma male/female/non-binary that does not follow rules? You do you. For the rest of you normies, I have another way. This technique is based on understanding how the computer actually encodes the characters we type into computers. This is why an understanding of Software Engineering fundamentals is crucial to your growth in Tech. If you’re looking to build those up, make sure you show up to Math Mondays.

Step 3: Indirectly converting chars to ints

So how do you do that?

All the keys you see on your keyboard (and many more), have been an associated integer with them in the ASCII table. For example, ‘a’ maps to 97 and ‘A’ maps to 65. This allows us computers with different architectures, fonts, and OSs to understand the text they are given. 0 maps to 48 (I know) and the nums from [0,9] map to [48,57]. Why am I telling you this?

You can take a character, and find out its ASCII code. In Python, this is done with the ord(char) function, but your language will have its own variant. After that, we just need to shift the ASCII number by 48, and we’re guucci. This would look like

(ord(char) - 48) #we are guanateed our input will only be digits

Notice, that we haven’t directly converted our input into ints. We’ve just shifted our ASCII values by a bit. That shift just happens to perfectly match up with what we need to give us an int.

Now to get to coding things up-

Step 4: Coding everything

Combining our insights so far, we have the code here.

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        
        if(num1=='0' or num2=='0'):
            #If you have any insanely large input, this will save you time
            return '0'
        
        num1_res = 0
        for char in num1:
#we are going from left to right. So we multiply by 10 to account for #decimal places
            num1_res = num1_res * 10 + (ord(char) - 48)
            
        num2_res = 0
        for char in num2:
            num2_res = num2_res * 10 + (ord(char) - 48)
            
        res = num1_res * num2_res
        
        return str(res)

By doing this, you don’t have to reverse the strings (which would add extra computation). Multiplying our current by 10 when going to the next digit, automatically takes care of making sure that the values have appropriate values. And you don’t need to worry about messy carry-overs.

Time Complexity- O(N1 + N2). We go through both strings to convert them. N1,N2 are the lengths of the two strings

Space Complexity- O(M), where M is the length of the res string. This is because we are storing res as a string in the end. Worst case scenaio- O(N1+N2)

Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.

Stay Woke. I’ll see you living the dream.

Go kill all,

Devansh <3

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75