How to multiply two strings in Python

In computer science and programming, dealing with large numbers and performing arithmetic operations on them without converting them to native data types can be a significant challenge. This is especially true when handling large datasets or working within constraints where built-in functions are unavailable or inefficient. Understanding how to manipulate numerical strings directly can provide more control and efficiency in such scenarios.

Problem statement

Calculate the product of two numbers, s1 and s2, given as strings. These numbers can be negative, and we can’t utilize any built-in function or convert the strings to integers. Zeros can appear at the beginning of numbers, and the ‘+’ sign does not need to be specified at the beginning of positive numbers.

Consider the strings "123" and "-456". They aim to compute their product, resulting in "-56088", without converting these strings to integers. Handling this problem requires string manipulation techniques to simulate multiplication as done by hand. This problem is significant in contexts where large numbers exceed typical data type limits or conversions are restricted due to specific constraints.

Sample input and output

Here is the sample input and output for the above problem:

Input
- s1 = "9876", s2 = "-543"
Output
- Product = "-5362668"

Algorithm

Consider the signs of the numbers and handle them correctly during the multiplication operation.
To calculate the product of two strings of numbers, apply the elementary school multiplication approach.
Begin multiplying each digit from the rightmost digit of one number by each digit of the other number as if we are performing manual multiplication.
Maintain a record of the intermediate products and add them together to get the final result.

Code example

def multiplyStrings(s1, s2):
    # Get the lengths of the input strings
    m, n = len(s1), len(s2)
    # Detect the sign of the result
    isNegative = (s1[0] == '-' and s2[0] != '-') or (s1[0] != '-' and s2[0] == '-')
    # Initialize the result list with zeros
    result = [0] * (m + n)
    # Multiplication Algorithm
    for i in range(m - 1, -1 + (s1[0] == '-'), -1):
        for j in range(n - 1, -1 + (s2[0] == '-'), -1):
            # Calculate the product of each digit
            mul = int(s1[i]) * int(s2[j]) + result[i + j + 1]
            result[i + j + 1] = mul % 10
            result[i + j] += mul // 10  # Handle carryovers
    # Find the position of the first non-zero digit
    startpos = next((i for i, x in enumerate(result) if x != 0), m + n)
    if startpos == m + n:
        return "0"
    # Adjust the result based on the sign
    if isNegative:
        return "-" + "".join(map(str, result[startpos:]))
    return "".join(map(str, result[startpos:]))
# Driver code to test the functionality
s1 = "9876";
s2 = "-543";
# Calculate the product of two strings
product = multiplyStrings(s1, s2)
# Display the result
print("Python Product:", product)

Multiply strings without using built-in functions or integer conversion

Code explanation

Here’s the explanation of the above code:

Lines 1–7: This defines a function multiplyStrings that takes two string arguments, s1 and s2. It calculates their lengths m and n, respectively. isNegative is a boolean that checks if the result of multiplication should be negative based on the signs of s1 and s2. The result is initialized as a list of zeros with a length of m + n.
Lines 10–15: This nested loop iterates through each digit of s1 and s2, starting from the least significant digit to the most significant digit. It computes the product of individual digits, considers any carryovers (mul // 10), and updates the result list accordingly.
Lines 18–25: After computing the product, startpos finds the index of the first non-zero digit in result. If all digits are zero, it returns "0". Depending on isNegative, it constructs the final result string by joining the non-zero digits in result, optionally prepending a minus sign if the result should be negative.
Lines 28–35: This part demonstrates the usage of multiplyStrings with example strings, s1 and s2, computes their product using the defined function and prints the result.

Complexity analysis

Let’s understand the efficiency of the algorithm:

Time complexity
- The method goes through the digits of the input strings once.
- Constant time operations are carried out during each iteration.
- Therefore, the time complexity is $O(a*b)$ , where a and b are the lengths of the input strings.
Space complexity
- The algorithm assigns a certain amount of extra space for variables (result array, isNegative, startIdx1, startIdx2, and mul.
- The amount of space needed is based on a few constant numbers and the length of the result array.
- Hence, the space complexity is $O(a + b)$ for storing the result.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments