Добуток масиву крім самого себе#937

Добуток масиву крім самого себе (Розбір)

Нехай $in$ — вхідний масив, індексацію почнемо з $1$ . Тоді вхідні числа зберігаються в $in [1], in [2], ..., in [n]$ in[1], in[2], ..., in[n]. Якщо обчислити добуток $p$ усіх елементів масиву $in$ , а потім покласти $o u t_{i} = p / i n_{i}$ out_i = p / in_i ( $o u t$ — результуючий масив), то такий метод не працює у випадку, коли $i n_{i} = 0$ in_i = 0.

Розглянемо інший підхід. Побудуємо два масиви:

Масив префіксних добутків $p r e f$ , в якому

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],

при цьому покладемо $p r e f [0] = 1$ pref[0] = 1;

Масив суфіксних добутків $s u f$ , в якому

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],

при цьому покладемо $s u f [n + 1] = 1$ suf[n + 1] = 1;

Тоді $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].

Приклад

Реалізація алгоритму

Оголосимо робочі масиви.

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

Читаємо вхідні дані.

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

Будуємо масив добутків префіксів.

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

Будуємо масив добутків суфіксів.

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

Будуємо результуючий масив.

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

Виводимо відповідь.

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