Минимизируйте произведение первых 2^K–1 натуральных чисел, меняя местами биты для любой пары любое количество раз
Для положительного целого числа K задача состоит в том, чтобы минимизировать положительное произведение первых ( 2K – 1) натуральных чисел, переставляя местами биты в соответствующих позициях любых двух чисел любое количество раз.
Примеры:
Input: K = 3
Output: 1512
Explanation: The original product is 5040. The given array in binary notation is {001, 010, 011, 100, 101, 110, 111}
- In the first operation swap the leftmost bit of the second and fifth elements. The resulting array is [001, 110, 011, 100, 001, 110, 111].
- In the second operation swap the middle bit of the third and fourth elements. The resulting array is [001, 110, 001, 110, 001, 110, 111].
After the above operations, the array elements are {1, 6, 1, 6, 1, 6, 7}. Therefore, the product is 1 * 6 * 1 * 6 * 1 * 6 * 7 = 1512, which is the minimum possible positive product.
Input: K = 2
Output: 6
Explanation: The original permutation in binary notation is {’00’, ’01’, ’10’}. Any swap will lead to product zero or does not change at all. Hence 6 is the correct output.
Подход: Данную задачу можно решить, исходя из наблюдения, что для получения минимального положительного произведения частота числа 1 должна быть максимальной при перестановке битов любых двух чисел. Выполните следующие шаги, чтобы решить данную проблему:
- Найдите значение диапазона как (2 K – 1) .
- Преобразование элементов range/2 в 1 путем сдвига всех битов нечетных чисел на четные числа, кроме 0 -го бита .
- Следовательно, числа диапазона/2 будут равны 1, а числа диапазона/2 будут равны диапазону – 1 , а последнее число в массиве останется таким же, как значение диапазона .
- Найдите результирующее произведение всех чисел, образованных на предыдущем шаге, как результирующее минимальное полученное положительное произведение.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(K)
Вспомогательное пространство: O(1)