Product of Array Except Self#937

Product of Array Except Self (Editorial)

Let $in$ be the input array, and let us use $1$ -based indexing. Then the input values are stored in $in [1], in [2], ..., in [n]$ in[1], in[2], ..., in[n]. If we compute the product $p$ of all elements of the array in and then set $o u t_{i} = p / i n_{i}$ out_i = p / in_i (where $o u t$ is the resulting array), this method fails when $i n_{i} = 0$ in_i = 0.

Let us consider a different approach. We construct two arrays:

• The prefix product array $p r e f$ , where

p r e f [i] = in [1] \cdot in [2] \cdot ... \cdot in [i],

pref[i] = in[1] \cdot in[2] \cdot ... \cdot in[i],

and we define $p r e f [0] = 1$ pref[0] = 1;

• The suffix product array $s u f$ , where

s u f [i] = in [i] \cdot in [i + 1] \cdot ... \cdot in [n],

suf[i] = in[i] \cdot in[i + 1] \cdot ... \cdot in[n],

and we define $s u f [n + 1] = 1$ suf[n + 1] = 1;

Then $o u t_{i} = p r e f [i - 1] \cdot s u f [i + 1]$ out_i = pref[i - 1] \cdot suf[i + 1].

Example

Algorithm implementation

Declare the arrays.

#define MAX 1000002
int in[MAX], pref[MAX], suf[MAX], res[MAX];

Read input data.

scanf("%d",&n);
for(i = 1; i <= n; i++)
  scanf("%d",&in[i]); // [1,2,3,4]

Build the array of prefix products.

pref[0] = 1;
for(i = 1; i <= n; i++) // [1,2,6,24]
  pref[i] = pref[i-1] * in[i];

Build the array of suffix products.

suf[n+1] = 1;
for(i = n; i >= 1; i--) // [24,24,12,4]
  suf[i] = suf[i+1] * in[i];

Build the resulting array.

for(i = 1; i <= n; i++)  // [24,12,8,6]
  res[i] = pref[i-1] * suf[i+1];

Print the answer.

for(i = 1; i <= n; i++)
  printf("%d ",res[i]);
printf("\n");