Минимизируйте произведение максимальных чисел в двух массивах с помощью свопов | Набор 2

Даны два массива arr1[] и arr2[] размера N каждый. Выберите любой индекс i и поменяйте местами элементы arr1[i] и arr2[i] . Применяя эту операцию любое количество раз (возможно, ни одного), найдите минимально возможное произведение максимальных элементов из массива arr1[] и arr2[] .

Примеры:

Input: N = 6
arr1[] = {1, 2, 6, 5, 1, 2}
arr2[] = {3, 4, 3, 2, 2, 5}
Output: 18
Explanation: Swap elements at index 1 and 5. So arr1[] and arr2[] become
{1, 4, 6, 5, 1, 5} and {3, 2, 3, 2, 2, 2} respectively. 
The maximum elements are 6 and 3 giving product as 18.

Input: N = 2
arr1[] = {1, 3}
arr2[] = {3, 1}
Output: 3
Explanation: Swap elements at index 1. arr1[] and arr2[] will become
{1, 1} and {3, 3}. The product of maximum elements will be 3.

Подход: Решение основано на простом наблюдении. Просто попробуйте перенести меньшие элементы в один массив, а большие в другой, используя своп. Это минимизирует максимальный элемент в одном массиве и приведет к минимальному продукту. Выполните шаги, указанные ниже:

• Здесь сначала выберите любой массив, либо arr1[] либо arr2[] (скажем, выбранный arr1[] ).
• Поменять местами все элементы с одинаковым индексом, но удовлетворяющие условию arr1[i] < arr2[i] (означает перенос более крупных элементов в arr1[] ).
• После замены всех пар между массивами arr1[] и arr2[] просто найдите максимум в обоих массивах.
• Теперь просто выведите произведение максимума обоих массивов.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(1)