How to Answer: How do you multiply strings without a leading-zero product?
Advice and answer examples written specifically for a Java Intermediate Level Implementation job interview.
2. How do you multiply strings without a leading-zero product?
This question focuses on Java iteration.
You are given two non-negative integers num1 and num2 in the form of strings. Your task is to find the product of num1 and num2 and return it in the form of a string. You can neither use in-built like BigIntger nor convert the numbers from strings to integers. The product must not have any leading zeros.
/*Example*/
Given num1 = “123†num2 = “45â€
Expected output: “5535â€Solution:
To solve this problem, we need to see how multiplication is done on pen-paper (focus on underlined digits). Let resultString be the resulting number in the form of string.
num1 = 1 2 3 index i of num1 (here i = 1)
num2 = 4 5 index j of num2 (here j = 0)
_______________________
1 5
1 0
0 5
1 2
0 8 index (i + j) and (i + j + 1)
0 4 of resultString (here 1 & 2)
______________________________
0 5 5 3 5
0 1 2 3 4 indices of resultString
It can be observed that the product of digits at indices i and j of num1 and num2 respectively is added to the indices (i + j) and (i + j + 1) of resultString. So we will iterate over each digit of the two numbers starting from unit places (that is we loop in reverse order) and find the product of the digits and store them at the appropriate location. To store the product of the digits, we use a result array. It can be observed that when two integers with digits count m and n are multiplied, the product has at most m + n number of digits.
We use the Integer.parseInt function to convert a digit into number form which is in string form initially. Thus Interger.parseInt(“2â€) = 2.
After looping over all the digits, the result may have leading zeros. So we check for one of the two conditions to remove the leading zeroes and add the middle zeroes: first is to check if they are zero or not and second if any non-zero digit has occurred. Then we keep on adding the characters to the resultant string.
class Solution {
public String multiply(String num1, String num2) {
int m = num1.length();
int n = num2.length();
int result[] = new int[m + n];
Arrays.fill(result, 0);
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int digit1 = Integer.parseInt(num1.substring(i, i+1));
int digit2 = Integer.parseInt(num2.substring(j, j+1));
int idx1 = i + j;
int idx2 = i + j + 1;
int mul = digit1 * digit2;
int sum = mul + result[idx2];
result[idx1] += Math.floor(sum / 10);
result[idx2] = sum % 10;
}
}
StringBuilder resultString = new StringBuilder("");
for (int i = 0; i < result.length; i++) {
if(result[i] != 0 || resultString.length() != 0) {
resultString.append(result[i]);
}
}
if(resultString.length() == 0) return "0";
return resultString.toString();
}
}m = length of num1
n = length of num2
Time complexity- O(m * n)
Space complexity- O(m + n)
Written by S. Kumar on June 27th, 2021