Multiply strings leetcode python

by

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

Question

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Multiply strings leetcode python

Constraints:

  • 1 <= num1.length, num2.length <= 200
  • num1 and num2 consist of digits only.
  • Both num1 and num2 do not contain any leading zero, except the number 0 itself.

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 = [0] * 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

READ MORE

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