Product Array Puzzle

Question

Problem: You are given an array of ‘N’ integers. You need to return another array ‘product’ such that ‘product[i]’ contains the product of all the arrays except the element at the ith position in the given array.

Note: As the product of elements can be very large you need to return the answer in mod (10^9+7).

My Code

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;
}

Doubt: I am not getting all the test cases passed. I think the issue is with handling large products. Could anyone help to suggest what changes should I make to get all test cases passed?

Answer 1

You will have to take modulo every time you calculate multiplications to prevent overflow.

Also casting to a 64-bit (or more) type is required if int is not capable to store the product before taling modulo.

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;
}