sundeepblue
4/21/2014 - 2:39 PM

Take an array of numbers and replace each item with the product of all the other items in the array

Take an array of numbers and replace each item with the product of all the other items in the array

#define ARRAY_MAX 30

// forget to consider integer overflow

void product_of_all_other_items_in_array(int A[], int N) {
    int aux1[ARRAY_MAX], aux2[ARRAY_MAX];
    
    aux1[0] = 1;
    for(int i=1; i<N; i++)
        aux1[i] = aux1[i-1] * A[i-1];
    
    aux2[N-1] = 1;
    for(int i=N-2; i>=0; i--)
        aux2[i] = aux2[i+1] * A[i+1]; // gist, should be A[i+1] not A[i-1]
        
    for(int i=0; i<N; i++) 
        A[i] = aux1[i] * aux2[i];
}

// solution 2, use less space
  vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> res(nums.size(), 1);
        for (int i = 1; i < nums.size(); ++i) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        int right = 1;
        for (int i = nums.size() - 1; i >= 0; --i) {
            res[i] *= right;
            right *= nums[i];
        }
        return res;
    }