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
andnum2
consist of digits only.Both
num1
andnum2
do not contain any leading zero, except the number0
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.
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.
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.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.