产品阵列拼图

Question

问题:给你一个包含“N”个整数的数组。您需要 return 另一个数组“product”，使得“product[i]”包含除给定数组中第 i 个位置的元素之外的所有数组的乘积。

注：由于元素的乘积可能非常大，因此您需要 return mod (10^9+7) 中的答案。

我的代码

vector < int > productPuzzle(vector < int > & arr, int n) {
   
   vector<int> output;
   int product = 1;
    for(int i=0;i<n;i++){
        product*=arr[i];
        output.push_back(product);
    }
    product = 1;
    for(int i=n-1;i>0;i--){
        output[i] = output[i-1]*product;
        product *= arr[i];
    }
    output[0] =product;
    return output;
}

疑问：我没有让所有的测试用例都通过。我认为问题在于处理大型产品。谁能帮助建议我应该进行哪些更改才能通过所有测试用例？

Answer 1

每次计算乘法时都必须取模以防止溢出。

如果 int 无法在计算模数之前存储产品，则还需要转换为 64 位（或更多）类型。

vector < int > productPuzzle(vector < int > & arr, int n) {
   const int MOD_BY = 1000000007;
   
   vector<int> output;
   int product = 1;
    for(int i=0;i<n;i++){
        product=(static_cast<long long>(product) * arr[i]) % MOD_BY;
        output.push_back(product);
    }
    product = 1;
    for(int i=n-1;i>0;i--){
        output[i] = (static_cast<long long>(output[i-1])*product) % MOD_BY;
        product = (static_cast<long long>(product) * arr[i]) % MOD_BY;
    }
    output[0] =product;
    return output;
}

产品阵列拼图

Product Array Puzzle

c++

arrays

algorithm

data-structures