Replace Every Array Element With The Product of Every Other Element

Posted in

Replace Every Array Element With The Product of Every Other Element
vinaykhatri

Vinay Khatri
Last updated on October 6, 2024

    Problem

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

    Approach 1

    We can easily solve this problem using the division operator. First, we keep the product of all the elements and then keep dividing this product with elements at each index. This will take O(N) time and O(1) auxiliary space. Let’s look at another approach as well.

    Approach 2

    This method consumes O(N) additional space and runs in O(N) time. The method is to compute the prefix and suffix arrays, as shown below. The solution is as simple as res [i] = prefix [i] * suffix [i] and return the res .

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    
    vector<int> productExceptSelf(vector<int>& nums) {
            int n=nums.size();
            int prefix[n];
            int suffix[n];
            prefix[0]=1;
            suffix[n-1]=1;
            int prod1=1;
            int prod2=1;
            for(int i=1;i<n;i++)
             { 
                prod1*=nums[i-1];
                prefix[i]=prod1; 
              }
              for(int i=n-2;i>=0;i--)
               {
                prod2*=nums[i+1];
                suffix[i]=prod2;
               }
            vector<int>ans;
            for(int i=0;i<n;i++){
                ans.push_back(prefix[i]*suffix[i]);
            }
            return ans;
        }
    int main(){
        vector<int>nums{1, 2, 3, 4};
        vector<int>ans=productExceptSelf(nums);
        for(auto itr:ans) cout<<itr<<" ";
    }

    C Programming

    #include<stdio.h>
    int ans[5];
    void replaceProduct(int* nums, int n)
    {
        int i;
        
        // use ans as dp (right to left)
        ans[n - 1] = nums[n - 1];
        for (i = n - 2; i >= 0; i--) {
            ans[i] = nums[i] * ans[i + 1];
        }
        
        for (i = 0; i < n; i++) {
            if (i == 0) {
                ans[0] = ans[1];
            } else if (0 < i && i < (n - 1)) {
                ans[i] = nums[i - 1] * ans[i + 1];
                nums[i] = nums[i] * nums[i - 1];
            } else {
                ans[i] = nums[i - 1];
            }
        }
    }
    void main(){
        int a[5] = {1, 2, 3, 4, 5};
        replaceProduct(a, 5);
        for(int i=0;i<5;i++) printf("%d ", ans[i]);
    }

    Python Programming

    def replaceProduct(nums):
        ans = [1] * len(nums)        
        for i in range(1, len(nums)):
            ans[i] = nums[i-1] * ans[i-1]
                
        prod2 = 1
        for i in range(len(nums)-1, -1, -1):
            ans[i] *= prod2
            prod2 *= nums[i]             
            
        return ans
    
    l = [1, 2, 3]
    print(replaceProduct(l))
    Output
    [6, 3, 2]

    People are also reading:

    Leave a Comment on this Post

    0 Comments