937. Произведение массива кроме самого себя

Имеется массив in из n целых чисел. Постройте массив out такой, что out_i равно произведению всех элементов массива in кроме in_i. Решите задачу за O(n) и с константной сложностью по памяти.

Вход. Первая строка содержит число n (1 < n ≤ 10⁶). Вторая строка содержит n целых чисел, каждое из которых по модулю не более 100.

Выход. Выведите массив out. Известно, что все выводимые числа не больше 2*10⁹.

Пример входа 1	Пример выхода 1
4 1 2 3 4	24 12 8 6
Пример входа 2	Пример выхода 2
4 2 0 1 4	0 8 0 0

РЕШЕНИЕ

массивы

Анализ алгоритма

Пусть in – входной массив, индексацию начнем с 1. То есть входные числа хранятся в in[1], in[2], …, in[n]. Если вычислить произведение p всех чисел из массива in, после чего положить out_i = p / in_i (out – результирующий массив), то такой метод не сработает если in_i = 0.

Рассмотрим другой подход. Построим два массива:

· Массив префиксов pref, в котором pref[i] = in[1] * in[2] * … * in[i], при этом положим pref[0] = 1;

· Массив суффиксов suf, в котором suf[i] = in[i] * in[i + 1] * … * in[n], при этом положим suf[n + 1] = 1;

Тогда out_i = pref[i – 1] * 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");