Product of Array Except Self

A Product Array Puzzle in Geeks

Description:

Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division operator and in O(n).

Example:

Example:
arr[] = {10, 3, 5, 6, 2}
prod[] = {180, 600, 360, 300, 900}

Idea:

• Method 1 Space O(n) Algorithm: 1) Construct a temporary array left[] such that left[i] contains product of all elements on left of arr[i] excluding arr[i]. 2) Construct another temporary array right[] such that right[i] contains product of all elements on on right of arr[i] excluding arr[i]. 3) To get prod[], multiply left[] and right[].

• Method 2 Space O(1)

use one temporary variable, and resue the result array

Note space can be optimized to O(1)

Code:

#include <vector>
#include <iostream>

using namespace std;

vector<int> arrayPuzzle(vector<int> arr1){
    int size1 = arr1.size();
    vector<int> left(size1, 1);
    vector<int> right(size1, 1);
    vector<int> result(size1, 1);

    for(int i=1; i<size1; ++i){
        left[i] = arr1[i-1] * left[i-1];
    }
    for(int j=size1-2; j>=0; --j){
        right[j] = arr1[j+1] * right[j+1];
    }

    for(int i=0; i<size1; ++i){
        result[i] = left[i] * right[i];
    }
    return result;
}

vector<int> arrayPuzzleNoSpace(vector<int> arr1){
    int size1 = arr1.size();
    vector<int> result(size1, 1);

    for(int i=1; i<size1; ++i){
        result[i] = arr1[i-1] * result[i-1];
    }
    int left = arr1.back();
    for(int j=size1-2; j>=0; --j){
        result[j] = left * result[j];
        left = left * arr1[j];
    }
    return result;
}

int main(){
    vector<int> arr = {10, 3, 5, 6, 2};

    for(auto elem: arrayPuzzle(arr)){
        cout<<elem<<' ';
    }
    cout<<endl;

    for(auto elem: arrayPuzzleNoSpace(arr)){
        cout<<elem<<' ';
    }


}