Multiply Two Strings in Java

Multiplying two strings in Java involves converting the strings representing numbers into integer values, performing the multiplication, and converting the result back into a string. This approach is particularly useful when dealing with very large numbers that exceed the range of primitive data types like int or long.

Input: String 1 = "123", String 2 = "45"

Output: "5535"

Explanation

The output "5535" is obtained by multiplying "123" and "45" as integers. Digit-by-digit multiplication, similar to manual calculation, produces intermediate sums, which are combined to form the final product. The result is then converted back into a string, accurately representing the multiplication of the two input strings as numbers.

Approach 1: Digit-by-Digit Multiplication with Result Array

Algorithm

Step 1: Handle Edge Cases: Check if either of the strings is "0". If yes, return "0" immediately because multiplying any number with zero results in zero.

Step 1.1: Check for Zero Inputs: If either of the input strings (num1 or num2) is equal to "0", the product will always be "0". This is because multiplying any number by zero results in zero. In this case, immediately return "0" without performing further calculations. This step ensures efficiency and avoids unnecessary processing.

Step 2: Initialize Variables: Calculate the lengths of both input strings, num1 and num2. Create an integer array result of size n1 + n2 to store the intermediate and final results of the multiplication. This size ensures it can accommodate the largest possible product of the two numbers.

Step 2.1: Calculate Lengths of Input Strings: Start by calculating the lengths of the two input strings, num1 and num2. This is essential for determining the size of the result array. The result array should be large enough to accommodate the largest possible product, which can have a length of n1 + n2.

Step 3: Simulate Manual Multiplication: Loop through the digits of num1 from right to left (like in manual multiplication). For each digit in num1, loop through the digits of num2 from right to left. Multiply the current digits of num1 and num2. It gives a partial product.

Step 4: Add Partial Product to Result Array: Compute the position in the result array where the partial product contributes. It depends on the indices of the digits in num1 and num2.

Add the partial product to the current value in the array, accounting for carry-over to the next position.

Step 5: Handle Carry-Over: After adding the partial product, determine the carry (sum divided by 10) and the remainder (sum modulo 10). Store the remainder in the current position of the result array and add the carry to the next higher position.

Step 6: Build the Result String: Traverse the result array from left to right and construct the final result string. Skip leading zeros during this process. If the result string is empty after skipping leading zeros, return "0".

Step 6.1: Traverse the Result Array: After all partial products and carry-overs are added to the result array, start from the leftmost position and traverse through the array. Convert each digit in the array to form the final result string. Skip any leading zeros to ensure the string represents the correct product.

Step 7: Return the Result: Once the result array is processed and leading zeros are removed, convert the remaining digits into a string. This string represents the final product of the two input strings. If the result string is empty after removing zeros, return "0" to handle the case of a zero product.

Let’s implement the above approach in a Java program.

File Name: StringMultiplication.java

Output:

 
5535   

Complexity Analysis

Time Complexity

The time complexity of this algorithm is O(n1 * n2), where n1 and n2 are the lengths of the two strings. It is because every digit in the first string is multiplied with every digit in the second string, resulting in a nested loop structure.

Space Complexity

The space complexity of this algorithm is O(n1 + n2), where n1 and n2 are the lengths of the two strings. It comes from the integer array used to store intermediate results, which has a maximum size of n1 + n2 to accommodate the largest possible product.

Approach 2: Using Divide and Conquer Method

Step 1: Base Case (Small Numbers): If the numbers are small (e.g., single digits), you simply multiply them directly. This is the easiest case and doesn't need the full algorithm.

Step 1.1: Base Case Check: When the numbers involved are very small, typically one-digit numbers, we skip the recursive multiplication process and directly multiply them. For example, multiplying "3" and "5" would directly give "15". This avoids unnecessary complexity and speeds up the process for small inputs.

Step 2: Splitting the Numbers: For larger numbers, you split each number into two parts. For example, if you are multiplying "1234" and "5678":

Split "1234" into two parts: high1 = "12" and low1 = "34".

Split "5678" into two parts: high2 = "56" and low2 = "78".

Step 3: Recursive Multiplication: Now, we need to calculate three smaller multiplications:

Multiply the high parts: high1 * high2 (i.e., 12 * 56).

Multiply the low parts: low1 * low2 (i.e., 34 * 78).

Multiply the sum of the high and low parts of each number: (high1 + low1) * (high2 + low2) (i.e. ., (12 + 34) * (56 + 78)).

Step 4: Combining the Results: After calculating the three products, you combine them to get the final result:

The first product (high1 * high2) is shifted to the left by two places (like multiplying by 100).

The second product ((high1 + low1) * (high2 + low2)) is adjusted by subtracting the first and third products and shifted by one place (like multiplying by 10).

Finally, add the third product (low1 * low2) directly. The results in a more efficient way of multiplying compared to traditional methods.

Step 4.1: Shift and Combine Products: After calculating the three products, we need to combine them into the final result. The first product (high1 * high2) is shifted left by two places, effectively multiplying it by 100. The second product, which represents the cross-multiplication of the high and low parts, is adjusted by subtracting the first and third products, then shifted left by one place. This ensures the proper placement of each product in the final result.

Step 5: Final Result: After combining the results, you get the final product. If there are any leading zeros, we remove them to get the correct answer.

Step 6: Build the Result String: Once all the partial products have been calculated and combined, the next step is to construct the final result string. You begin by traversing the result array, starting from the leftmost digit. As you form the string, make sure to skip any leading zeros. If, after skipping zeros, the string is empty, return "0" to handle cases where the result is zero.

Let’s implement the above approach in a Java program.

File Name: KaratsubaMultiplication.java

Output:

 
5453149   

Complexity Analysis

Time Complexity

The Karatsuba algorithm improves multiplication by breaking the problem into smaller parts. Instead of performing O(n²) operations like traditional multiplication, it reduces the complexity to O(^1.585 ). This means Karatsuba can multiply large numbers faster, as it requires fewer steps for the same size of input.

Space Complexity

The space complexity of the program is O(n), where n is the number of digits in the input numbers. This is because the algorithm only needs space for storing intermediate results and recursive calls, which grow linearly with the size of the input numbers.