Multiply String

Introduction to Multiply String

"Multiply String" is a function that performs a specific task in programming: the multiplication of strings. This may not be a typical operation in mathematics, but in programming, it's a common task that can be used for various purposes such as creating repeated patterns, formatting output, and more.The problem typically involves multiplying two non-negative integers represented as strings and returning the result as a string. This problem is interesting because it requires implementing the multiplication operation manually, similar to how it is done on paper.

Overview of Multiply String

The function takes two input strings. The first string is the one that needs to be repeated, and the second string is an integer in string format that indicates the number of repetitions. The output of the function is a new string which is the first input string repeated a number of times specified by the second input string. The function handles possible exceptions such as non-integer second inputs and returns an error message in such cases.

Code

# copyrights to venkys.io
# for more information visit https://venkys.io/
# Python program to Multiply String 
# TimeComplexity:O(m*n)
# SpaceComplexity:O(m+n)
def multiply(num1, num2):
    # Initialize result variable to store the final product
    res = 0
    ans=""
    # Iterate through each digit of the first number in reverse order
    for i in range(len(num1) - 1, -1, -1):
        x = int(num1[i])  # Get the current digit of the first number
        ans = ""
        carry = 0  # Initialize carry for the multiplication
        # Iterate through each digit of the second number in reverse order
        for j in range(len(num2) - 1, -1, -1):
            y = int(num2[j])  # Get the current digit of the second number
            product = (x * y) + carry  # Calculate the product of the current digits and add carry
            carry = product // 10  # Update carry for the next iteration
            ans += str(product % 10)  # Add the last digit of the product to the result
        x= "0" * (len(num1) - i - 1)
        ans = x + ans  # Append zeros based on the position of the current digit in the first number
        if carry:
            ans += str(carry)  # If there is a carry after the inner loop, add it to the result
        res += int(ans[::-1])  # Add the current partial product to the final result

    return str(res)

if __name__ == "__main__":
    num1 = input()
    num2 = input()
    print(multiply(num1, num2))

Step-by-Step Explanation

The function starts by initializing res and ans variables to 0 and an empty string respectively. res will eventually hold the result of the multiplication, and ans will be used to store intermediate results.
The outer loop traverses the first input string in reverse order. Each digit in num1 will be multiplied with each digit in num2.
Inside the outer loop, x is set as the integer value of the current digit in num1.
The inner loop, nested inside the outer loop, also traverses the second input string in reverse order.
Inside the inner loop, y is set as the integer value of the current digit in num2. Then, product is calculated as the multiplication of x and y plus any carry from the previous calculation.
The carry is then updated to be the integer division of product by 10.
The remainder of product divided by 10 is then added to the ans string.
After the inner loop, a string x is created with as many zeros as the current index in num1.
This string x is then prepended to the ans string to account for place values in the multiplication.
If there is still a value in carry after the inner loop has finished, this value is added to ans.
The current ans string is then reversed and converted to an integer, after which it is added to res.
After all loops, the function returns res as a string, which is the result of the multiplication.
The main part of the code is where the function is called with num1 and num2 as arguments, and the result is printed.

Code

//copyrights to venkys.io
//for more information visit https://venkys.io/
//Java program to Multiply String 
//TimeComplexity:O(m*n)
//SpaceComplexity:O(m+n)
import java.util.Scanner;
public class Main{
    // Function to multiply two numbers represented as strings
    static String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        // Array to store the product of each digit multiplication
        int[] pos = new int[m + n];
       // Nested loops for multiplying each digit of num1 with each digit of num2
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                // Calculate the product of the current digits
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
                // Determine positions for storing the current digit product in the result array
                int p1 = i + j, p2 = i + j + 1;
                // Add the current product to the existing sum at the determined positions
                int sum = mul + pos[p2];
                // Update the positions in the result array considering the carry
                pos[p1] += sum / 10;
                pos[p2] = (sum) % 10;
            }
        }  
        // Build the final result string using StringBuilder
        StringBuilder sb = new StringBuilder();
        for(int p : pos) 
        // Skip leading zeros and append the digits to the result
        if(!(sb.length() == 0 && p == 0)) sb.append(p);
        // If the result is empty, return "0", otherwise return the result string
        return sb.length() == 0 ? "0" : sb.toString();
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String num1 = scanner.nextLine();
        String num2 = scanner.nextLine();
        // Print the result of multiplying num1 and num2
        System.out.println(multiply(num1,num2));
    }
}

Step-by-Step Explanation

The function 'multiply' begins by determining the length of both input strings 'num1' and 'num2'. It then initializes an array 'pos' with a size equal to the sum of the lengths of 'num1' and 'num2'. This array will hold the results of the individual multiplications.
Two nested for-loops are used to traverse both strings from right to left (from least significant digit to most significant). The outer loop iterates through each digit in 'num1', and the inner loop iterates through each digit in 'num2'.
Inside the inner loop, the current digits of 'num1' and 'num2' are multiplied together to get 'mul'.
'p1' and 'p2' are indices for positions in the 'pos' array. 'p1' is for the carry from the multiplication, and 'p2' is for the result of the multiplication.
The sum of 'mul' and the current value at 'pos[p2]' is computed and added to 'pos[p1]' and 'pos[p2]' as the carry and result of the multiplication respectively.
After the nested loops, the array 'pos' has computed digits of the result in reverse order. A StringBuilder is used to convert 'pos' into a string.
The StringBuilder 'sb' iterates through 'pos' and appends each digit to 'sb'. It skips leading zeros.
Finally, if 'sb' is empty (which means that 'num1' or 'num2' was zero), the function returns "0". Otherwise, it returns the string in 'sb', which is the result of the multiplication.
In the main part of the code, 'num1' and 'num2' are defined, the 'multiply' function is called with 'num1' and 'num2' as arguments, and the result is printed out.

Code

/*copyrights to venkys.io*/
/*for more information visit https://venkys.io/ */
/*CPP program to Multiply String */
/*TimeComplexity:O(m*n)*/
/*SpaceComplexity:O(m+n)*/
#include <bits/stdc++.h>
/* Function to multiply two numbers represented as strings*/
std::string multiply(std::string num1, std::string num2)
{
    int m = num1.length(), n = num2.length();
    int pos[m + n]{0};
    /* Nested loops for multiplying each digit of num1 with each digit of num2 */
    for (int i = m - 1;i>=0;i--){
        for(int j=n-1;j>=0;j--){
            /* Calculate the product of the current digits*/
            int mul = (num1[i] - '0') * (num2[j]-'0');
            /* Determine positions for storing the current digit product in the result array*/
            int p1 = i+j, p2 = i+j+1;
            /* Add the current product to the existing sum at the determined positions*/
            int sum = mul + pos[p2];
            /* Update the positions in the result array considering the carry*/
            pos[p1] += sum/10;
            pos[p2] = (sum) % 10;
        }
    }
    /* Build the final result string*/
    std::string ans = "";
    for(int p :pos) 
        /* Skip leading zeros and append the digits to the result*/
        if(!(ans.length() == 0 && p==0))ans+=std::to_string(p);
     /* If the result is empty, return "0", otherwise return the result string*/
    return ans.length() == 0 ? "0" : ans;
}

int main()
{
    std::string num1;
    std::getline(std::cin, num1);
    std::string num2;
    std::getline(std::cin, num2);
    /* Print the result of multiplying num1 and num2*/
    std::cout << multiply(num1, num2);
    return 0;
}

Step-by-Step Explanation

The C++ implementation of the 'multiply' function closely follows the logic of the Java implementation.

The function 'multiply' begins by determining the length of both input strings 'num1' and 'num2'. It then initializes an array 'pos' with a size equal to the sum of the lengths of 'num1' and 'num2'. This array will hold the results of the individual multiplications.
Two nested for-loops are used to traverse both strings from right to left (from least significant digit to most significant). The outer loop iterates through each digit in 'num1', and the inner loop iterates through each digit in 'num2'.
Inside the inner loop, the current digits of 'num1' and 'num2' are multiplied together to get 'mul'.
'p1' and 'p2' are indices for positions in the 'pos' array. 'p1' is for the carry from the multiplication, and 'p2' is for the result of the multiplication.
The sum of 'mul' and the current value at 'pos[p2]' is computed and added to 'pos[p1]' and 'pos[p2]' as the carry and result of the multiplication respectively.
After the nested loops, the array 'pos' has computed digits of the result in reverse order. A string 'ans' is used to convert 'pos' into a string.
The string 'ans' iterates through 'pos' and appends each digit to 'ans'. It skips leading zeros.
Finally, if 'ans' is empty (which means that 'num1' or 'num2' was zero), the function returns "0". Otherwise, it returns the string in 'ans', which is the result of the multiplication.
In the main part of the code, 'num1' and 'num2' are defined, the 'multiply' function is called with 'num1' and 'num2' as arguments, and the result is printed out.

Time and Space Complexity Analysis

The time complexity of the Multiply String function is O(m*n), where m and n are the lengths of the input strings. This is because the function uses two nested loops to iterate through each digit in both strings.

The space complexity of the function is also O(m+n) because an array of size m+n is used to store the results of the individual multiplications.

Real World Applications of Multiply String

In Scientific Computing: In scientific computing, large numbers (that can't be handled by standard data types) are often represented as strings. The Multiply String function can be used to perform multiplication operations on these large numbers.
In Cryptography: In cryptography, strings are often used to represent keys and other cryptographic elements. The Multiply String function can be used in the encryption and decryption processes.
In Graphics Programming: In graphics programming, the Multiply String function can be used to create patterns or to repeat elements.
In Web Development: The Multiply String function can be used in web development to generate repeated elements in HTML or CSS, or to manipulate strings in server-side programming.

Test Cases

Input:
"123"
"456"
Output:
"56088"

Explanation: The product of 123 and 456 is 56088.
Input:
"999"
"999"
Output:
"998001"

Explanation: The product of 999 and 999 is 998001.
Input:
"1234"
"5678"
Output:
"7006652"

Explanation: The product of 1234 and 5678 is 7006652.