Задача о преобразовании массива с целыми числами

Исходные данные: массив с числами типа Integer. Вам нужно написать функцию, которая на входе получит исходный массив, а на выходе вернет массив, в котором каждое значение получено путем произведения всех значений исходного массива с отличным от текущего индексом.

Для ясности приведем пример. Допустим, исходный массив имеет вид:

Тогда функция должна вернуть:

Расчет значений происходит следующим образом:

Дополнительные условия:

  • Нельзя использовать деление.
  • Функция должна быть с наименьшими затратами памяти и времени выполнения.

Решение

Для того, чтобы вычислить возвращаемый массив без использования деления, мы дважды пройдемся по массиву. Проходя первый раз, мы будем получать произведение всех значений до текущего индекса и сохранять это произведение в отдельном массиве poducts_of_all_ints_except_at_index. В этом же массиве будем сохранять результат произведения всех значений после текущего индекса, но уже идя в обратном порядке. Ответ же мы получим, перемножив значения перед и после индекса во время обратного прохода по массиву.

Код решения (на Python):

Сложность полученного алгоритма — O(n) по памяти и O(n) по времени. Свои варианты предлагайте в комментариях.

Источник: Interview Cake