Multiply Strings In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Close-up of a computer screen displaying programming code in a dark environment.

Problem Statement: Multiply Strings

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

Note:

  • The integers num1 and num2 are non-negative, and they can be as large as 10^4 digits long.
  • You should not convert the input strings to integers and multiply them directly (i.e., avoid using int(num1) * int(num2)).

Example:

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Example 3:

Input: num1 = "0", num2 = "0"
Output: "0"

Approach:

Multiplying large numbers represented as strings without converting them to integers can be achieved using the standard method of multiplication that we learn in elementary school: long multiplication.

Here’s the step-by-step breakdown:

  1. Understanding the Problem:
    • Given two numbers num1 and num2 as strings, we need to multiply them and return the result as a string.
    • Instead of directly converting the strings to integers, we simulate the process of multiplying each digit of num1 with each digit of num2.
  2. Basic Idea:
    • Place Value: When you multiply a digit from num1 with a digit from num2, the product should be added at the appropriate position based on its place value.
    • For example, multiplying num1 = "123" and num2 = "456":
      • Multiply each digit of num1 with each digit of num2, and keep track of the results.
      • The result will be added to an array, where the indices represent place values (units, tens, hundreds, etc.).
    • Final Step: Convert the array back to a string by handling carry-over and ensuring that the result is correct.
  3. Step-by-Step Process:
    • Create an array result where result[i] will store the sum of products for the place value i.
    • Multiply each digit of num1 with each digit of num2, and place the result in the correct position in the result array.
    • After multiplying, handle any carries and construct the final string.

Algorithm:

  1. Edge Case: If either num1 or num2 is "0", return "0" immediately.
  2. Result Array: Initialize a result array of size len(num1) + len(num2) to hold the intermediate results.
  3. Multiply Digits: For each digit in num1 and num2, multiply them and add the result to the appropriate position in the result array.
  4. Handle Carry: After multiplication, propagate any carries in the result array.
  5. Convert to String: Convert the result array to a string, removing any leading zeros.

Code Implementation:

Python:

def multiply(num1: str, num2: str) -> str:
    # Edge case: if either number is "0", the result is "0"
    if num1 == "0" or num2 == "0":
        return "0"
    
    # Initialize the result array with zeros. The maximum length of the result
    # can be at most len(num1) + len(num2).
    result = [0] * (len(num1) + len(num2))
    
    # Reverse num1 and num2 to make the multiplication easier
    num1 = num1[::-1]
    num2 = num2[::-1]
    
    # Perform multiplication
    for i in range(len(num1)):
        for j in range(len(num2)):
            # Multiply digits and add to the corresponding position in the result array
            product = int(num1[i]) * int(num2[j])
            result[i + j] += product
            result[i + j + 1] += result[i + j] // 10  # Carry to the next position
            result[i + j] %= 10  # Keep only the single digit at the current position
    
    # The result array now contains the digits of the product in reverse order.
    # We need to remove any leading zeros.
    # Convert the result to a string
    result = result[::-1]
    # Skip leading zeros
    result_str = ''.join(map(str, result)).lstrip('0')
    
    return result_str

Explanation of the Code:

  1. Edge Case Check:
    • If either of the input strings is "0", the result is immediately "0", because any number multiplied by zero is zero.
  2. Result Array:
    • The result array is initialized with zeros and has a size of len(num1) + len(num2). This is because the maximum length of the product of two numbers can be at most the sum of the lengths of the two numbers.
  3. Reversing the Strings:
    • We reverse num1 and num2 so that we can process the digits starting from the least significant digit (rightmost digit), making the multiplication simpler.
  4. Multiplying Digits:
    • We multiply each digit from num1 and num2. The product is placed in the appropriate position in the result array, and we handle carries by propagating them to the next index in the array.
  5. Handling Carries:
    • After adding the product to the corresponding position in result, we handle the carry by moving the overflow to the next position in the result array.
  6. Constructing the Final Result:
    • Once all multiplications and carries are processed, we reverse the result array back to the correct order and convert it into a string.
    • We use .lstrip('0') to remove any leading zeros from the result.

Time and Space Complexity:

  • Time Complexity: O(m * n), where m and n are the lengths of num1 and num2, respectively. We perform two nested loops, one for each digit in num1 and num2, resulting in a time complexity of O(m * n).
  • Space Complexity: O(m + n), where m and n are the lengths of num1 and num2. We use a result array of size m + n to store intermediate results.

Example Walkthrough:

Example 1:

Input: num1 = "123", num2 = "456"
  • Step 1: Initialize result array with zeros: [0, 0, 0, 0, 0, 0] (length len(num1) + len(num2)).
  • Step 2: Reverse num1 and num2: num1 = "321", num2 = "654".
  • Step 3: Multiply each pair of digits and update the result array:
    • 3 * 6 = 18, place 8 in result[0] and carry 1 to result[1].
    • 3 * 5 = 15, plus carry 1, place 16 in result[1] and carry 1 to result[2].
    • Continue for all pairs of digits.
  • Step 4: Propagate carries and convert the result array into the final string "56088".

Edge Case Examples:

Example 2:

Input: num1 = "0", num2 = "123"
  • Since one of the numbers is "0", the result is "0" immediately.

Example 3:

Input: num1 = "999", num2 = "999"
  • The result will be "998001" after performing the multiplication.

Conclusion:

The Multiply Strings problem is solved by simulating the long multiplication process. This method avoids the use of built-in integer multiplication and provides an efficient solution with a time complexity of O(m * n). By handling carries and constructing the result step by step, we can multiply large numbers represented as strings and return the result as a string.