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

<p><strong>Note:</strong>&nbsp;You must not use any built-in BigInteger library or convert the inputs to integer directly.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> num1 = "2", num2 = "3"
<strong>Output:</strong> "6"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> num1 = "123", num2 = "456"
<strong>Output:</strong> "56088"
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num1.length, num2.length &lt;= 200</code></li>
	<li><code>num1</code> and <code>num2</code> consist of digits only.</li>
	<li>Both <code>num1</code> and <code>num2</code>&nbsp;do not contain any leading zero, except the number <code>0</code> itself.</li>
</ul>

class Solution {
public:
    string multi(string num1,char ch,string ans){

        int n = num1.size();

        int i=n-1;
        int carry = 0;
        while(i>=0){
            int a = num1[i]-'0';
            int b = ch-'0';

            int c = a*b + carry;
            int dig = c%10;
            c /= 10;
            carry = c;
            ans += to_string(dig);
            i--;
        }

        if(carry!=0)
        ans += to_string(carry);

        reverse(ans.begin(),ans.end());

        return ans;
    }

    string add(string s,string t){
        int n = s.size();
        int m = t.size();

        int i=n-1,j=m-1;
        string ans = "";
        int carry = 0;

        cout<<s<<" "<<t<<"  ";
        while(i>=0 && j>=0){
            int a = s[i]-'0';
            int b = t[j]-'0';

            int c = a+b+carry;
            int dig = c%10;
            ans += to_string(dig);
            c /= 10;
            carry = c;
            i--;
            j--;
        }

        while(i>=0){
            int a = s[i]-'0';
            int c = a+carry;
            int dig = c%10;
            ans += to_string(dig);
            c /= 10;
            carry = c;
            i--;
        }

         while(j>=0){
            int b = t[j]-'0';
            int c = b+carry;
            int dig = c%10;
            ans += to_string(dig);
            c /= 10;
            carry = c;
            j--;
        }

        ans += to_string(carry);

        reverse(ans.begin(),ans.end());

        return ans;
    }
    string multiply(string num1, string num2) {
        
        int n = num1.size();
        int m = num2.size();
        string temp = "";
        string ans = "";
        for(int i=m-1;i>=0;i--){
            auto str = multi(num1,num2[i],temp);
            temp += "0";
            ans = add(ans,str);
        }

        if(ans.size()>1){
            for(int i=0;i<ans.size();i++){
                if(ans[i]!='0'){
                    return ans.substr(i);
                }
            }
            return "0";
        }

        return ans;
    }
};
17625