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

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

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

			[1, 7, 3, 4]
		

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

			[84, 12, 28, 21]
		

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

			[7*3*4, 1*3*4, 1*7*4, 1*7*3]
		

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

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

Решение

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

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

			def get_products_of_all_ints_except_at_index(int_list):

    # создаем дополнительный массив с таким же размером, что и исходный.
    products_of_all_ints_except_at_index = [None] * len(int_list)

    # Находим произведение всех значений до текущего.
    # Результат помещаем в новый массив.
    product_so_far = 1
    i = 0
    while i < len(int_list):
        products_of_all_ints_except_at_index[i] = product_so_far
        product_so_far *= int_list[i]
        i += 1

    # Находим произведение всех значений после текущего,
    # при этом двигаясь по массиву в обратную сторону.
    # Параллельно вычисляем значение текущей ячейки.
    product_so_far = 1
    i = len(int_list) - 1
    while i >= 0:
        products_of_all_ints_except_at_index[i] *= product_so_far
        product_so_far *= int_list[i]
        i -= 1

    return products_of_all_ints_except_at_index
		

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

Источник: Interview Cake