Sponsored
Sponsored
This approach mimics the multiplication process that is taught in schools. The idea is to multiply each digit of num1 with each digit of num2 and store the result in the corresponding position in an array. This intermediate result is then summed together to form the final product. We avoid using any built-in library functions for handling large numbers.
Time complexity: O(n * m), where n and m are the lengths of num1 and num2 respectively.
Space complexity: O(n + m) for the result array used to store intermediate results.
1public String multiply(String num1, String num2) {
2 if (num1.equals("0") || num2.equals("0")) return "0";
3 int[] result = new int[num1.length() + num2.length()];
4
5 for (int i = num1.length() - 1; i >= 0; i--) {
6 for (int j = num2.length() - 1; j >= 0; j--) {
7 int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
8 int sum = mul + result[i + j + 1];
9
10 result[i + j + 1] = sum % 10;
11 result[i + j] += sum / 10;
12 }
13 }
14
15 StringBuilder sb = new StringBuilder();
16 for (int num : result) {
17 if (!(sb.length() == 0 && num == 0)) {
18 sb.append(num);
19 }
20 }
21 return sb.toString();
22}The Java solution follows a similar logic to the Python solution, using an integer array to keep track of each digit's contribution to the final number. The process involves iterating over each digit of the input strings, multiplying them, and managing the carry directly within the loop.
This approach leverages string manipulation and direct indexing to carefully manage carries and keep track of the multiplication progression similarly to approach one. The ultimate goal is to achieve better space optimization by minimizing the auxiliary storage.
Time complexity: O(n * m), comparable to previous method.
Space complexity: O(n + m) but implemented to handle carry more elegantly.
1public String multiplyNumbers(String num1, String num2)
Adopted string and array manipulations ensure the effective harnessing of Java's StringBuilder while performing similar operations as in Python to handle carries and intermediate multiplications directly.