Если деление разрешено, можно использовать общее произведение, отдельно обработав нули: без нулей делим на текущий элемент, с одним заполняем только его позицию, с двумя и более возвращаем нули.
Можно ли решить Product of Array Except Self проще, если разрешено использовать любые операции?
Если деление разрешено, можно использовать общее произведение, отдельно обработав нули: без нулей делим на текущий элемент, с одним заполняем только его позицию, с двумя и более возвращаем нули.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Если деление разрешено, можно использовать общее произведение, отдельно обработав нули: без нулей делим на текущий элемент, с одним заполняем только его позицию, с двумя и более возвращаем нули.
Сначала посчитайте количество нулей и произведение ненулевых элементов. При единственном нуле произведение остальных находится только на его позиции; на всех других позициях результат включает этот ноль. Время O(n), дополнительная память O(1), если не считать выходной массив. Для целых чисел нужно точное целочисленное деление; также учитывайте переполнение произведения.