Найдите K такое, что сумма расстояний Хэмминга между K и каждым элементом массива минимальна.
Дан массив arr[] из N неотрицательных целых чисел и целое число P (1 ≤ P ≤ 30) , которое обозначает верхний предел любого числа в массиве (2 P – 1) . Задача состоит в том, чтобы найти такое число, чтобы сумма расстояний Хэмминга между самим числом и всеми числами в массиве была минимальной. Если возможных ответов несколько, выведите любой из них.
Примечание. Расстояние Хэмминга между двумя числами — это количество позиций в их двоичном представлении, в которых биты чисел различны.
Примеры:
Input: N = 4, P = 4
arr[] = {12, 11, 8, 10}
Output: 8
Explanation: The number 8 has minimum sum of hamming distances.
Hamming distance from 12: 1
Hamming distance from 11: 2
Hamming distance from 8: 0
Hamming distance from 10: 1
10 can also be a valid answer.Input: N = 3, P = 3
arr[] = {5, 2, 7}
Output: 7
Подход: Эту проблему можно решить, используя жадный подход и манипулирование битами. Наблюдая, можно сказать, что в окончательном ответе будут установлены только те биты, которые имеют большее количество 1 для всех элементов массива по сравнению с 0. Потому что в противном случае общая сумма разных битов будет увеличиваться. Выполните шаги, указанные ниже, чтобы решить проблему:
- Создайте двумерный массив bits[][] , чтобы вести подсчет битов для всех чисел в каждой из P битовых позиций.
- Начните перебирать массив с самого начала.
- Для каждого элемента массива увеличьте количество битов для каждого установленного бита в массиве bits[][] .
- После завершения итерации проверьте общее количество установленных битов в массиве битов .
- Если количество установленных битов в позиции больше, чем количество нулей в этой битовой позиции, установите этот бит в результирующем числе как 1, иначе как 0.
- Верните финальное число в качестве результата.
Иллюстрация:
For example take the array, arr[] = {12, 11, 8, 10} and P = 4.
Now see the bit representation of the numbers in the following image:Logical Representation
From the above image it can be clearly seen that the least significant bit has more number of 0s compared to 1s.
Similarly 3rd bit and the most significant bit have more number of 0s and 1s respectively.
But the 2nd bit has same number of 0s and 1s.
So the resultant number can have binary representation 1010 or 1000 i.e. it can be 10 or 8.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N * P)
Вспомогательное пространство: O(N * P)