Replace Every Array Element With The Product of Every Other Element

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:

• WAP to Count no. of alphabets, digits and spaces present in a file
• Majority Element
• Check for pairs in an array with a particular sum
• WAP to Print Square Using * Character
• Count all Possible Paths from Top Left to Bottom Right in a Matrix
• How to find and remove loops in a Linked List?
• Find minimum jumps required to reach the destination
• Difference Between Repeater, DataList and GridView
• Convert a Binary Tree to Doubly Linked List
• Print all subarrays with 0 sum