Вопрос на интервью по решению задач (массивы)

Существует массив целых чисел, скажем, 3,5,7,9. Вы должны создать другой массив и заполнить его так, чтобы 0-я позиция второго массива была произведением всех чисел из первого массива, за исключением числа в его 0-й позиции, что означает, что оно должно быть 5x7x9 (исключая 3), число в индексе 1 из второго массива будет произведением 3x7x9 (исключая 5).

Первый ответ, который пришел мне в голову, был иметь 2 цикла for, что приведет к временной сложности O (n2). Позже я вычислил это:

Умножая все числа в первом массиве (3x5x7x9) и заполняя второй массив, я делю этот продукт на число в этой позиции. разделите на 3, если я заполняю 0-ю позицию, разделите на 5, если я заполняю 1-ю позицию, и так далее. Это снизит сложность с O (n2) до, вероятно, O (2n).

Но интервьюер говорит, что деление не допускается. Я не мог думать ни о чем другом, кроме как хранить различные возможные кратные в какой-то структуре данных и использовать их при заполнении. Я сдался, но когда его спросили, он сказал, что будет поддерживать 2 массива прямых и обратных кратных. Когда его спросили о проблеме сложности решения, он сказал, что его можно оптимизировать.