43. Multiply Strings (LeetCode) (solution: C++, C#)

Problem Name: 43. Multiply Strings
Problem Link: https://leetcode.com/problems/multiply-strings/
Difficulty: Medium
Tag: Math | String
Language: C# | C++
OJ: LeetCode

Algorithm:
Initialization:
  • Create two arrays, multiply_dig and add, both of size maxPosition, where maxPosition is calculated as (num1.length() * num2.length()) + 1.
  • Initialize each element in add to 0.
Nested Loop for Multiplication:
  • Use nested loops to iterate through each digit of num2 (outer loop) and num1 (inner loop).
  • Calculate the product of the current digits from num1 and num2, considering any carry from the previous digit.
  • Update the multiply_dig array with the calculated values.
Adding Intermediate Results:
  • After each inner loop (i.e., after processing one digit of num2), add the intermediate results stored in multiply_dig to the add array.
  • Handle any carry during addition.
Traversing add Array:
  • Traverse the add array from the beginning.
  • Ignore leading zeros until a non-zero digit is encountered.
  • Concatenate the non-zero digits to the answer string.
Check for Result "0":
  • If the answer string is empty (all zeros), return "0".
  • Otherwise, return the calculated result.
Code(C#)
public class Solution
{
    public string Multiply(string num1, string num2)
    {
        int maxPosition = (num1.Length * num2.Length)+1;
        int[] multiply_dig = new int[maxPosition];
        int[] add = new int[maxPosition];
        string answer = "";

        for (int i = 0; i < maxPosition; i++)
            add[i] = 0;

        for (int i = num2.Length - 1, startPosition = maxPosition - 1; i >= 0; i--, startPosition--)
        {
            for (int j = 0; j < maxPosition; j++)
                multiply_dig[j] = 0;
            int carry = 0;
            int position = startPosition;

            for (int j = num1.Length - 1; j >= 0; j--)
            {
                int value = ((num1[j] - '0') * (num2[i] - '0')) + carry;
                multiply_dig[position] = (value % 10);
                position--;
                carry = value / 10;
            }
            while (carry != 0)
            {
                multiply_dig[position] = carry % 10;
                position--;
                carry /= 10;
            }

            carry = 0;
            for (int j = maxPosition - 1; j >= 0; j--)
            {
                int value = add[j] + multiply_dig[j] + carry;
                add[j] = value % 10;
                carry = value / 10;
            }
        }

        bool flag = false;
        for(int i=0; i<maxPosition; i++)
        {
            if(add[i] == 0 && !flag) continue;
            else
            {
                answer += ((char)(add[i]+'0'));
                flag = true;
            }

        }

        if(answer=="") return "0";
        return answer;
    }
}

Code(C++)
class Solution {
public:
    string multiply(string num1, string num2) {
        int maxPosition = (num1.length() * num2.length()) + 1;
        int* multiply_dig = new int[maxPosition];
        int* add = new int[maxPosition];
        std::string answer = "";

        for (int i = 0; i < maxPosition; i++)
            add[i] = 0;

        for (int i = num2.length() - 1, startPosition = maxPosition - 1; i >= 0; i--, startPosition--) {
            for (int j = 0; j < maxPosition; j++)
                multiply_dig[j] = 0;
            int carry = 0;
            int position = startPosition;

            for (int j = num1.length() - 1; j >= 0; j--) {
                int value = ((num1[j] - '0') * (num2[i] - '0')) + carry;
                multiply_dig[position] = (value % 10);
                position--;
                carry = value / 10;
            }
            while (carry != 0) {
                multiply_dig[position] = carry % 10;
                position--;
                carry /= 10;
            }

            carry = 0;
            for (int j = maxPosition - 1; j >= 0; j--) {
                int value = add[j] + multiply_dig[j] + carry;
                add[j] = value % 10;
                carry = value / 10;
            }
        }

        bool flag = false;
        for (int i = 0; i < maxPosition; i++) {
            if (add[i] == 0 && !flag)
                continue;
            else {
                answer += static_cast<char>(add[i] + '0');
                flag = true;
            }
        }

        if (answer == "")
            return "0";
        return answer;
    }
};