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.
1def multiply(num1: str, num2: str) -> str:
2 if num1 == '0' or num2 == '0':
3 return '0'
4
5 result = [0] * (len(num1) + len(num2))
6
7 for i in range(len(num1) - 1, -1, -1):
8 for j in range(len(num2) - 1, -1, -1):
9 mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
10 p1, p2 = i + j, i + j + 1
11
12 summation = mul + result[p2]
13 result[p2] = summation % 10
14 result[p1] += summation // 10
15
16 result_str = ''.join(map(str, result))
17 return result_str.lstrip('0')This Python solution uses an array (list) to store the intermediate results of each single-digit multiplication. We iterate backwards over both numbers, calculate the multiplication of individual digits, and manage the carry for each step. The results are stored from the least significant to the most significant position.
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.
1def multiply_numbers(num1: str, num2: str)
Optimized through direct multiplication with preexisting carries within the innermost loop, this approach does not drastically alter the foundational logics compared to approach one, yet reduces redundancy in carry handling.