Integer Multiply

EPI

Description:

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

nums can be negative.

Example:

[1,2,3,4] * [-2,3,4] -> [-2,8,8,7,5,6]

Idea:

num1 size1, num2 size2

num1 * num2 最大 size ＝ size1 + size2

Code:

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// 先reverse，算好再reverse回来，index好弄一些

vector<int> integerMultiply(vector<int> num1, vector<int> num2){
    int size1=num1.size();
    int size2=num2.size();

    int sign = num1[0] * num2[0] > 0 ? 1 : -1;

    num1[0] = abs(num1[0]);
    num2[0] = abs(num2[0]);

    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());

    vector<int> result(size1+size2, 0);

    for(int i=0; i<size1; i++){
        for(int j=0; j<size2; j++){
            result[i+j] += num1[i] * num2[j];
            result[i+j+1] += result[i+j]/10;
            result[i+j] %= 10; 
        }
    }

    while(!result.empty() && result.back() == 0){
        result.pop_back();
    }

    if (result.empty()){
        return vector<int>(1,0);
    }

    reverse(result.begin(), result.end());
    result[0] *= sign;

    return result;

}

// 倒着乘，有点麻烦
vector<int> integerMultiplyBackward(vector<int> num1, vector<int> num2){
    int size1=num1.size();
    int size2=num2.size();

    int sign = num1[0] * num2[0] > 0 ? 1 : -1;

    num1[0] = abs(num1[0]);
    num2[0] = abs(num2[0]);

    vector<int> result(size1+size2, 0);

    for(int i=size1-1; i>=0; i--){
        for(int j=size2-1; j>=0; j--){
            result[i+j+1] += num1[i] * num2[j];
            result[i+j] += result[i+j+1]/10;
            result[i+j+1] %= 10; 
        }
    }

    int i = 0;
    while(i<result.size() && result[i] == 0){
        i++;
    }

    result.erase(result.begin(), result.begin()+i);

    if ( result.empty() ){
        return vector<int>(1,0);
    }

    result[0] *= sign;
    return result;

}

int main(){
    vector<int> num1={-1,2,3,4,5};
    // vector<int> num2={1,2,3};
    vector<int> num2={0};

    for(auto elem: integerMultiply(num1, num2)){
        cout<<elem<<' ';
    }
    cout<<endl;

    for(auto elem: integerMultiplyBackward(num1, num2)){
        cout<<elem<<' ';
    }

}