LeetCode Solution: Product of Array Except Self Problem

In this tutorial, we will cover the solution for the Leetcode problem of Product of Array Except Self Problem. Before moving on to the solution, let's understand the problem first.

Problem Statement:

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Explanation:

In this problem, we are given an array of int and are asked to replace each element of the array by the product of all the element except itself.

For example:

If input array is:

[1,2,3,4]

Then the output array should be:

[24,12,8,6]

a[0] = a[1]* a[2] * a[3] = 2*3*4

a[1] = a[0]* a[2] * a[3] = 1*3*4

a[2] = a[0]* a[1] * a[3] = 1*2*4

a[3] = a[0]* a[1] * a[2] = 1*2*3

Logic for Solution:

There are 3 different cases that we need to handle here:

1. Number of zeros are exactly 0

2. Number of zeros are exactly 1

3. The number of zeros are 2 or more.

Let's look at the way to tackle each of them one at a time and then you will be able to relate the code written below in C++.

So let's dive deep into it!

The below code remains common to evaluate each of the three mentioned cases:

int i = 0;
int j = nums.size();
int p = 1, f = 1, c = 0, k = 0; 
while(i != j)
{
    p*=nums[i];
    if(nums[i]==0)
    {
        c++;
        k = i;
    }
    i++;
}
printf("%d", k);
printf("%d", p);
printf("%d", c);
i = 0;

Case 1: The number of zeros is exactly 0

• In this case, the simplest way is to first store the product of all the numbers of the array in a separate variable.

• Now, starting from the first number and moving to the last, let's modify each of the elements to the product of all the terms of the array except itself.

• This can be done by diving the product of all the elements by the element itself.

• This will give us the resulting number i.e. product of all the numbers except itself.

The code that handles this case is mentioned below:

else
{
    i=0;
    while(i!=j)
    {
        nums[i]=p/nums[i];
        i++;
    }    
}

Case 2: Number of zeros is exactly 1

• In this case, each of the modified element of the array will be 0, except for the one which itself is 0.

• To handle this case, let's first count the number of zeros in the array while checking each of the elements, and if 0, then increment the count of 0s.

• Also, store the index of the first 0 in the array in a separate variable, as this would be the index that has to be the product of all the remaining except self.

• Except for this number, all the other numbers of the modified array will be 0, as they will have the only 0 of the array as one of the elements in the multiplication.

The code that handles this case is mentioned below:

else if(c==1)
{
    i=0;
    p=1;
    while(i!=j)
    {
        if(i!=k)
            p=p*nums[i];
        i++;
    }
    i=0;     
    while(i!=j)
    {
        if(i==k)
            nums[i]=p;
        else
            nums[i]=0;
        i++;
    }
}

Case 3: Number of zeros are 2 or more

• This case is the simplest to handle, as logically, all the elements of the modified array will be 0, reason being, that each element will have at least one 0 (except for self) while taking the product of all the other elements.

• Even the 0s will have the other 0s as one of the elements in their product.

• So simply, Iterate a loop and equate all the elements of the array to 0.

The code to handle this case is mentioned below:

if(c > 1)
{
    while(i!=j)
    {
        nums[i]=0;
        i++;
    }
}

Putting it all together, here is the entire code that covers all the possible scenarios, and hence the final solution to the given problem:

class Solution {
    public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {   
        int i=0;
        int j=nums.size();
        int p=1,f=1,c=0,k=0;
        
        while(i!=j)
        {
            p*=nums[i];
            if(nums[i]==0)
            {
               c++;
                k=i;
            }
            i++;
        }
        printf("%d",k);
        printf("%d",p);
        printf("%d",c);
        i=0;
        
        if(c>1)
        {
            while(i!=j)
        {
            nums[i]=0;
            i++;
        }
            
        }
        else if(c==1)
        {
            i=0;
            p=1;
            while(i!=j)
            {
                if(i!=k)
                    p = p*nums[i];
                i++;
            }
            i=0;
            while(i!=j)
            {
                if(i==k)
                    nums[i]=p;
                else
                    nums[i]=0;
                i++;
            }
        }
        else
        {
            i=0;
            while(i!=j)
            {
                nums[i] = p/nums[i];
                i++;
            }
        }
        return nums;
    }
};

We hope that this step by step explanation to handle each of the possible scenario, might have helped you to understand the entire solution to the mentioned problem.

In case of any query, you can reach out to us via Email or can directly post your queries in the comments section down below.

You may also like:

• LeetCode Solution - First Bad Version Problem

• LeetCode Solution: Maximum Subarray Problem

• LeetCode Solution: Best Time to Buy and Sell Stock Problem

• LeetCode Solution: Move Zeroes Problem