Достаточно двух наименьших и двух наибольших элементов. Минимум произведений этих пар и пары минимум × максимум учитывает положительные, отрицательные числа и нули.
Дана последовательность целых чисел.
Достаточно двух наименьших и двух наибольших элементов. Минимум произведений этих пар и пары минимум × максимум учитывает положительные, отрицательные числа и нули.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
""" Дана последовательность целых чисел. Необходимо найти минимально возможное произведение пары элементов последовательности (пара - два каких-то элемента, не обязательно подряд идущие). Например, для последовательности чисел 9 4 2 5 3 ответ будет 6. """
def find_min_product(arr: list[int]) -> int: ...
Ответ
Достаточно двух наименьших и двух наибольших элементов. Минимум произведений этих пар и пары минимум × максимум учитывает положительные, отрицательные числа и нули.
def find_min_product(arr):
if len(arr) < 2:
raise ValueError('at least two elements required')
low = sorted(arr[:2])
high = low[:]
for value in arr[2:]:
low = sorted(low + [value])[:2]
high = sorted(high + [value])[-2:]
return min(low[0] * low[1], high[0] * high[1], low[0] * high[1])
Если есть оба знака, нужна наиболее отрицательная и наибольшая положительная величина. При одном знаке достаточно крайних пар. Повторяющиеся значения учитываются как разные элементы. Алгоритм выполняет O(n) работы; показанный arr[2:] создаёт O(n) временную память, которую можно убрать обходом индексов.