# Product of Array Except Self

(Leetcode)

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

The product of any prefix or suffix of `nums` 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: nums = [1,2,3,4]Output: [24,12,8,6]`

Example 2:

`Input: nums = [-1,1,0,-3,3]Output: [0,0,9,0,0]`

# Approach

1. Using the division operator

Time Complexity = O(n*n) where n is the size of the given array/ vector

Space Complexity = O(n) where you will store the values in a vector

`LOGIC : Multiply the other elements except nums[i], for eg : arr = [1,2,3] so for ans = 2*3 = 6ans = 1*3 = 3 ans = 1*2 = 2 that is multiply the other elements except that element , so use the concept of using two loops. PS : Try to write on your own :) `

2. Without using the division operator

Time Complexity = O(n) where n is the size of the given array or vector

Space Complexity = O(n)

`LOGIC INVOLVED :1. I am using two vectors - one to store the left product and the other to store the right product. For eg :Taking the example [1,2,3]Left Product is the product of all elements to the left of the given number , leftProduct= 1 (initialise all elements with 1)leftProduct=leftProduct*nums = 1*1 = 1leftProduct=leftProduct*nums = 1*2 = 2Similarly , rightProd = 1 (initialise all elements with 1)rightProduct=rightProduct*nums = 1*3 = 3rightProduct=rightProduct*nums = 3*2 = 6nums = leftProduct*rightProd = 1*6 = 6nums = leftProduct*rightProd = 1*3 = 3nums = leftProduct*rightProd = 2*1 = 2CODE :class Solution {public:    vector<int> productExceptSelf(vector<int>& nums) {                vector<int>leftProd(nums.size(),1);        vector<int>rightProd(nums.size(),1);                for(int i=1;i<nums.size();i++)            leftProd[i]=leftProd[i-1]*nums[i-1];                for(int i=nums.size()-1;i>=1;i--)            rightProd[i-1] = rightProd[i]*nums[i];                for(int i=0;i<nums.size();i++)            nums[i] = leftProd[i]*rightProd[i];                return nums;    }};`

Hope this helps! Keep coding!

Since you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati

--

--