Searching and Sorting: Product of array except itself.

Problem Statement:

You are given an array, you need to return an array of the product such that the prod[i] is equal to the product of all the element of arr[] except arr[i].

Example

Input = {1, 2, 3, 4, 5}
O/p = {120, 60, 40, 30, 24}

2 * 3 * 4 * 5 product of other array elements except 1 is 120
1 * 3 * 4 * 5 product of other array elements except 2 is 60
1 * 2 * 4 * 5 product of other array elements except 1 is 40
1 * 2 * 3 * 5 product of other array elements except 1 is 30
1 * 2 * 3 * 4 product of other array elements except 1 is 24

Solution

This problem can be solved by different methods:

Method 1. Taking 2 extra arrays

In this method, we take 2 arrays, the first array stores the product of all the array elements from start to that index.
Another array to store the product of all the array elements from the end to that array index.
To get the product excluding that index, multiply the lhs array product upto index i-1 to the rhs array product upto index i+1.

Time Complexity is O(n)

Method 2. Taking 1 extra arrays

Instead of taking 2 arrays to store lhs, rhs,, in this solution we store the lhs and rhs product in the output array.
Thus reducing the space.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;


vector<int> product_except_self_two_arrays(vector<int>& nums) 
{
  vector<int> lhs(nums.size(), 1);
  vector<int> rhs(nums.size(), 1);
  for(int i = 1; i < nums.size();i++)
  {
      lhs[i] = lhs[i-1] * nums[i-1];
  }
  
  for(int i = nums.size()-1 ; i >= 1 ; i--)
  {
      rhs[i-1] = rhs[i] * nums[i];
  }
  
  for(int i = 0;i<nums.size() ;i++)
  {
      nums[i] = lhs[i] * rhs[i];
  }
  return nums;
}

vector<int> product_except_self_one_arrays(vector<int>& nums) 
{
  vector<int> lhs(nums.size(), 1);
  int rhs = 1;
  
  for(int i = 1; i<nums.size() ; i++)
  {
      lhs[i] = lhs[i-1] * nums[i-1];
  }
  
  for(int i = lhs.size()-1; i >= 1 ; i--)
  {
      rhs *= nums[i];
      lhs[i-1] *= rhs;
  }
  return lhs;
}

int main()
{
  vector<int> nums; 
    nums.push_back(1); 
    nums.push_back(2); 
    nums.push_back(3); 
    nums.push_back(4); 
    nums.push_back(5); 

  vector<int> result = product_except_self_two_arrays(nums); 


    cout << "\nProduct of array using 2 arrays "; 
    for (int i = 0; i < result.size(); i++) 
        cout << result[i] << " "; 

    vector<int> nums1; 
    nums1.push_back(1); 
    nums1.push_back(2); 
    nums1.push_back(3); 
    nums1.push_back(4); 
    nums1.push_back(5); 
    
    result = product_except_self_one_arrays(nums1); 

    cout << "\nProduct of array using 1 arrays "; 
    for (int i = 0; i < result.size(); i++) 
        cout << result[i] << " "; 

    return 0;
}

Output:

Product of array using 2 arrays 120 60 40 30 24
Product of array using 1 arrays 120 60 40 30 24

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *