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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5char *multiply(char *num1, char *num2) {
6 if (strcmp(num1, "0") == 0 || strcmp(num2, "0") == 0) return "0";
7 int len1 = strlen(num1), len2 = strlen(num2);
8 int *result = (int *)calloc(len1 + len2, sizeof(int));
9
10 for (int i = len1 - 1; i >= 0; i--) {
11 for (int j = len2 - 1; j >= 0; j--) {
12 int mul = (num1[i] - '0') * (num2[j] - '0');
13 int sum = mul + result[i+j+1];
14
15 result[i+j+1] = sum % 10;
16 result[i+j] += sum / 10;
17 }
18 }
19
20 char *resultStr = (char *)malloc((len1 + len2 + 1) * sizeof(char));
21 int pos = 0, k = 0;
22 while (pos < len1 + len2 && result[pos] == 0) pos++;
23 while (pos < len1 + len2) resultStr[k++] = result[pos++] + '0';
24 resultStr[k] = '\0';
25
26 free(result);
27 return resultStr;
28}The C version uses dynamic memory allocation to implement the array for the intermediate results. We iterate over the digits in the same manner as before, updating the array with the multiplication results and handling carries accordingly.
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.