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.