# 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**

- 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[0] = 2*3 = 6

ans[1] = 1*3 = 3

ans[2] = 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[0]= 1(initialise all elements with 1)

leftProduct[1]=leftProduct[0]*nums[0] = 1*1 = 1

leftProduct[2]=leftProduct[1]*nums[1] = 1*2 = 2Similarly , rightProd[2] = 1(initialise all elements with 1)

rightProduct[1]=rightProduct[2]*nums[2] = 1*3 = 3

rightProduct[0]=rightProduct[1]*nums[1] = 3*2 = 6nums[0] = leftProduct[0]*rightProd[0] = 1*6 = 6

nums[1] = leftProduct[1]*rightProd[1] = 1*3 = 3

nums[2] = leftProduct[2]*rightProd[2] = 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 ☕