Product of array except self

Table of Contents

Problem Statement

“Product of array except self” problem, states that you are given an array a [ ]. Print another array p [ ] of the same size such that value at i’th index of array p is equal to the product of all the elements of the original array except element at i’th index in array a.

Example

Product of array except self

a [ ] = {1, 2, 3}

{6, 3, 2}

Explanation: Since the array size is 3. If we multiply the 2nd & 3rd element, the product is 6. Similarly, we do this for the 2nd & 3rd index elements. Thus the output is {6, 3, 2}.

a [ ] = {4, 6, 1, 2}

{12, 8, 48, 24}

Using Division Method

This method is only effective in the case where all the array elements are always greater than 0.

Algorithm

1. Initialize an array a[] of size n.
2. Initialize a variable prod and store product of all the elements of the array a[] in it.
3. Create another array p[] to store products of all elements except self.
4. Traverse through array a[] and update the value of array p[] such that p[i] is equal to the division of a[i] and prod.
5. Print the array p[].

The problem can be solved if we use a variable to store the product of all the numbers (elements in the array, input). Then the answer for each element can be found if divide the current element from the total multiplication (i.e. the product of all the elements).

Code

C++ Program for product of array except self

#include <bits/stdc++.h>
using namespace std;

void prodArray(int a[], int n){
    int p[n], prod=1;
    
    //Find product of all elements of a[]
    for(int i=0; i<n; i++){
        prod = prod * a[i];
    }
    
    //Create array p[] to store
    //product except self
    for(int i=0; i<n; i++){
        p[i] = prod / a[i];
    }
    
    for(int i=0; i<n; i++){
        cout<<p[i]<<" ";
    }
}

int main() {
  int a[] = {4, 6, 1, 2};
  int n = sizeof(a)/sizeof(a[0]);
  prodArray(a,n);
  return 0;
}

12 8 48 24

Java Program for product of array except self

class product{
    
    void prodArray(int a[], int n){
        int p[] = new int[n], prod=1;
        
        //Find product of all elements of a[]
        for(int i=0; i<n; i++){
            prod = prod * a[i];
        }
        
        //Create array p[] to store
        //product except self
        for(int i=0; i<n; i++){
            p[i] = prod / a[i];
        }
        
        for(int i=0; i<n; i++){
            System.out.print(p[i] + " ");
        }
    }
    
    public static void main(String[] args){
        product pro = new product();
    	int a[] = {4, 6, 1, 2};
    	int n = a.length;
    	pro.prodArray(a,n);
    }
}

12 8 48 24

Complexity Analysis

Time Complexity

O(N), where the number of elements is N. Because here first we traversed through the array which makes the algorithm run in O(N) time.

Space Complexity

O(1), because we used constant extra space. But the program as a whole takes O(N) space since we stored the input.

Without Division Method

Algorithm for Product of array except self problem

1. Initialize an array a[] of size n and a variable prod as 1.
2. Create another array p[] of the same size with all the elements as 1.
3. Traverse all the values from starting index to last index and update the values of array p[] such that p[i] = prod and prod = prod * a[i].
4. Initialize prod as 1 again and start traversing the array from last index to starting index.
5. Update array p[] such that p[i] = prod and prod = prod * a[i].
6. Print the array p[].