Multiply two non-negative integer strings [with a twist]
My solution to this week's interview question from cassidoo's weekly newsletter.
Question:
Given two non-negative integers n1 and n2 represented as strings, return the product of n1 and n2, also represented as a string. Twist: You can’t use any built-in language integer libraries nor convert the inputs to integers directly.
Example:
$ stringProduct("123", "456")
$ "56088"
Solution:
public static int productOfTwoStrings(String s1, String s2) {
int n1 = 0;
for(int i=s1.length()-1; i>=0; i--) {
int n = s1.charAt(i)-48;
n1 = n1+ (n * ((int) Math.pow(10, s1.length()-i-1)));
}
int n2 = 0;
for(int i=s2.length()-1; i>=0; i--) {
int n = s2.charAt(i)-48;
n2 = n2+ (n * ((int) Math.pow(10, s2.length()-i-1)));
}
return n1*n2;
}
Time complexity: O(n) where n is the length of the longest string in the input.
(an interactive replit is available at the end of the post and you can run the code from there!)
Explanation:
charAt()
gives us the character representation of a character at a given index. For example, if we have the String s1="123"
, s1.charAt(0)
will give us '1'
. Notice the single quotes representing a character type.
Given the ASCII character table, we can see the the character representing the number '0'
has a value of 48.
So, doing '0' - 48
would give us the integer value 0
.
If we start traversing the string inputs from the end to the beginning, we need to multiply the integer value that we calculated by a power of 10 to make sure our resulting total integer is correct.