LeetCode has a Medium coding Problem in Its’ Algorithm Section “Multiply strings leetcode python”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE
Given two non-negative integers
num2 represented as strings, return the product of
num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
1 <= num1.length, num2.length <= 200
num2consist of digits only.
num2do not contain any leading zero, except the number
Solution to Multiply strings leetcode python
Both numbers’ multiplication begins with the ones place digit (the right-most digit), thus we should begin our multiplication at index num2.size() – 1 and work our way down to index 0. Alternatively, we may iterate from index 0 to index num2.size() – 1 by reversing both inputs.
We’ll obtain a new intermediate result for each digit in num2 that we multiply by num1. Depending on the language, this intermediate result (currentResult) will be kept in a list, string, or StringBuilder. To compute each intermediate result, we’ll start by inserting the proper amount of zeros in the second number, based on the current digit’s position (i.e. if it is the hundreds place, we append 2 zeros). Then, as shown in the diagrams above, we’ll do the multiplication step. We will enter the lower place digits into the currentResult before the higher place numbers during this phase. Our result will be in reverse order since we are pushing the lower place digits first and always appending to the end, so after the multiplication and addition processes are completed, we will need to invert the answer before returning.
Complete Solution in Python3
class Solution: def multiply(self, num1: str, num2: str) -> str: if num1 == "0" or num2 == "0": return "0" # Reverse both numbers. first_number = num1[::-1] second_number = num2[::-1] # For each digit in second_number, multipy the digit by first_number and then # store the multiplication result (reversed) in the results array. results =  for index, digit in enumerate(second_number): results.append(self.multiply_one_digit(digit, index, first_number)) # Add all of the results together to get our final answer (in reverse order) answer = self.sum_results(results) # Reverse answer and join the digits to get the final answer. return ''.join(str(digit) for digit in reversed(answer)) def multiply_one_digit(self, digit2: str, num_zeros: int, first_number: List[str]) -> List[int]: """Multiplies first_number by a digit from second_number (digit2).""" # Insert zeros at the beginning of the current result based on the current digit's place. current_result =  * num_zeros carry = 0 # Multiply each digit in first_number with the current digit of the second_number. for digit1 in first_number: multiplication = int(digit1) * int(digit2) + carry # Set carry equal to the tens place digit of multiplication. carry = multiplication // 10 # Append last digit to the current result. current_result.append(multiplication % 10) if carry != 0: current_result.append(carry) return current_result def sum_results(self, results: List[List[int]]) -> List[int]: # Initialize answer as a number from results. answer = results.pop() # Add each result to answer one at a time. for result in results: new_answer =  carry = 0 # Sum each digit from answer and result. Note: zip_longest is the # same as zip, except that it pads the shorter list with fillvalue. for digit1, digit2 in zip_longest(result, answer, fillvalue=0): # Add current digit from both numbers. curr_sum = digit1 + digit2 + carry # Set carry equal to the tens place digit of curr_sum. carry = curr_sum // 10 # Append the ones place digit of curr_sum to the new answer. new_answer.append(curr_sum % 10) if carry != 0: new_answer.append(carry) # Update answer to new_answer which equals answer + result answer = new_answer return answer
Python-related posts Visit HERE
C++ related posts Visit HERE
Databases related posts Visit HERE
Data Structures related posts visit HERE
Algorithms related posts visit HERE
Data Science related posts visit HERE