Arrays: Product of array except itself

Problem Statement:

You are given an array of integer, you need to return the product of the given array elements except itself.

You should not use division operator ‘/’

Example:

Input: N = 5, arr[] = {1,2,3,4,5}
Output: 120 60 40 30 24

Explanation:
—————-

for arr[0], except for the 0th index, take the product of whole array, i.e. [2 * 3 * 4 * 5] = 120

for arr[1], except for the 1th index, take the product of whole array, i.e. [1 * 3 * 4 * 5] = 60

for arr[2], except for the 2th index, take the product of whole array, i.e. [1 * 2 * 4 * 5] = 40

for arr[3], except for the 3th index, take the product of whole array, i.e. [1 * 2 * 3 * 5] = 30

for arr[4], except for the 4th index, take the product of whole array, i.e. [1 * 2 * 3 * 4] = 42

Solution 1: Using prefix and suffix array.

Before we look into the solution, we will understand what is prefix and suffix array:

Prefix array:

We will start from first index of the array and then multiply element one by one and store in the prefix array.

Suffix array:

We will start from the end and multiply elements one by one and store them into the suffix array.

Then to get the answer we will multiply each element index of both prefix and suffix array together,

Formula for prefix array:

prefix[i] = prefix[i-1] * arr[i-1]

Initialize all the elements of the prefix array as 1.

prefix = [1, 1, 1, 1, 1]

prefix[0] = 1 // initial starting of the array.

as prefix [0] is 1, we will start with i index = 1.

Pass 0:

i = 1

prefix[1] = prefix[i-1] * arr [i-1]
		  = prefix[0] * arr[0]
		  = 1 * 1 = 1

current prefix array =  [1, 1, 1, 1, 1]

Pass 1:

i = 2

prefix[2] = prefix[i-1] * arr [i-1]
		  = prefix[1] * arr[1]
		  = 1 * 2 = 1

current prefix array =  [1, 1, 2, 1, 1]

Pass 2:

i = 3

prefix[2] = prefix[i-1] * arr [i-1]
		  = prefix[2] * arr[2]
		  = 2 * 3 = 6

current prefix array =  [1, 1, 2, 6, 1]

Pass 3:

i = 4

prefix[2] = prefix[i-1] * arr [i-1]
		  = prefix[3] * arr[3]
		  = 6 * 4 = 24

current prefix array =  [1, 1, 2, 6, 24]

Formula for suffix array:

suffix[i] = suffix[i+1] * arr[i+1]

Initialize all the elements of the suffix array as 1.

suffix = [1, 1, 1, 1, 1]

suffix[n-1] = 1 // initial starting of the array.

as suffix [4] is 1, we will start with i index = 3.

Pass 0:

i = 3

suffix[3] = suffix[i+1] * arr[i+1]
		  = suffix[4] * arr[4]
		  = 1 * 5 = 1

current suffix array =  [1, 1, 1, 5, 1]

Pass 1:

i = 2

suffix[2] = suffix[i+1] * arr[i+1]
		  = suffix[3] * arr[3]
		  = 5 * 4 = 20

current suffix array =  [1, 1, 20, 5, 1]

Pass 2:

i = 1

suffix[1] = suffix[i+1] * arr[i+1]
		  = suffix[2] * arr[2]
		  = 20 * 3 = 60

current suffix array =  [1, 60, 20, 5, 1]

Pass 3:

i = 0

suffix[0] = suffix[i+1] * arr[i+1]
		  = suffix[1] * arr[1]
		  = 60 * 2 = 120

current suffix array =  [120, 60, 20, 5, 1]

Now that our both of the arrays are created, now we will multiply both of the array by index and we will get the result.

[120, 60, 40, 30, 24]

Time Complexity: O(n)

Space Complexity: O(n) + O(n)

Code Solution [enable the “enable_logs” tag to get the detailed description]

#include <iostream>
#define enable_logs 0
using namespace std;

void get_product (int arr[], int product[],int n)
{
    int prefix[n];
    prefix[0] = 1; // as first element can have no prefix
    
    for(int i = 1; i < n; i ++)
    {
        prefix[i] = prefix[i-1] * arr[i-1];
        
#if enable_logs
        cout <<"i = "<<i<<endl;
        cout << "prefix[i-1] = "<<prefix[i-1] << " arr[i-1] = "<<arr[i-1]<<endl;
        cout << "prefix [i] = "<<prefix[i]<<endl<<endl;;
#endif

    }
    
    int suffix[n];
    suffix[n-1] = 1; // as last element can have no suffix
    
    for(int i=n-2 ; i >= 0; i--)
    {
        suffix[i] = suffix[i+1] * arr[i+1];
#if enable_logs
        cout <<"i = "<<i<<endl;
        cout << "suffix[i+1] = "<<suffix[i+1] << " arr[i+1] = "<<arr[i+1]<<endl;
        cout << "suffix [i] = "<<suffix[i]<<endl<<endl;;
#endif
    }
    
    for(int i=0;i<n;i++)
    {
        product[i] = prefix[i] * suffix[i];
    }
}

int main()
{
    int arr[] = { 1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    int product[n];
    get_product(arr,product,n);
 
    cout << "Solution: ";
    for(int i=0;i<n;i++)
    {
        cout<<product[i]<<" , "; 
    }
    cout<<endl;
 
    return 0;
}

Output

Solution: 120 , 60 , 40 , 30 , 24 ,