Product of Array Except Self Python C++

Are you looking to solve and get the solution of Product of Array Except self? This is a very common interview question in the Software Engineering field by big companies.

Question:

Given an integer array numberArray, return an array result such that result[i] is equal to the product of all the elements of nums except  numberArray [i].

The product of any prefix or suffix  numberArray is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: numberArray = [4,5,6,7]
Output: [210,168,140,120]

Example 2:

Input: numberArray = [-2,-4,1,5,6]
Output: [-120,-60,240,48,40]

Product of Array Except Self Python Solution

Let me show you the solution for this question in Python. Then after that, we can discuss the algorithm for this question.

class Solution(object):
    def productExceptSelf(self, numberArrray):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = [1]
        for number in numberArrray:
            res.append(res[-1]*number)
        b = 1   
        for i in range(len(numberArrray)):
            res[len(numberArrray)-i-1] = res[len(numberArrray)-i-1] * b
            b = b* numberArrray[len(numberArrray)-i-1]
        return res[0:-1]

Algorithm:

You have to go through the array for the first time where you will store the multiplication of the numbers from the second index of the resultant number.

So, basically we are setting res[0] as 1 and then storing the multiplication of res[0]*num[0] in res[1]. With this res = [1,2,6,24].

In the second iteration, we will be iterating in reverse order and multiplying res[0] with the previous value stored in r_prod that is the multiplication of r_prod and numberArray[i].

Product of Array Except Self C++ Solution

Below is the solution to the above problem in C++.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& numberArray) {
        vector<int> res(numberArray.size(),1);
        for(int j=0;j<numberArray.size();j++){
            if(j==0) res[j] = 1;
            else res[j] = res[j-1]*numberArray[j-1];
        }
        int r_prod = 1;
        for(int i=numberArray.size()-1; i>=0; i--){
            res[i] *= r_prod;
            r_prod *= numberArray[i];
        }
        return res;
    }
};
Product of Array Except Self Python C++

If you liked the answer for Find First And Last Position of Element in Sorted Array then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview-related questions? Check Top Interview Questions category.

Leave a Comment