Ссылка на проблему
Вам дается массив A, состоящий из N целых чисел и целого числа X. Ваша цель состоит в том, чтобы в массиве было как можно больше равных целых чисел. Для достижения этой цели вы можете выполнить следующую операцию:
- Выберите индекс i (1≤i≤N) и установите⊕X, где ⊕ обозначает побитовую операцию xor.
Найдите максимальное количество равных целых чисел, которые вы можете иметь в конечном массиве, и минимальное количество операций для получения этого множества равных целых чисел.
Ограничение:
- 0 ≤ X ≤ 10^9
- 0 ≤ Ai ≤ 10^9
Input: x = 2, arr = [1,2,3] Output: [2,1] One way to obtain 2 equal integers is to set A1=A1⊕2 =1⊕2=3. So the array becomes [3,2,3]. There is no way to obtain 3 equal integers in the final array.
Важной частью этой проблемы является отслеживание количества встречаемости каждого числа и количества операций, необходимых для этого числа. Поэтому мы будем использовать две хэш-карты. Мы сопоставляем число с вхождением и число с операциями. Предположим, что наш массив будет выглядеть как [1,2,3], тогда в начале наши карты будут выглядеть следующим образом.
Counter {1:1,2:1,3:1}
Operations {1:0,2:0,3:0}
Следующий шаг – зациклить массив и преобразовать каждое число в заданное значение XOR, затем соответствующим образом обновить счетчик и операции. Примечание:
- А КСОР
- А КСОР
- А КСОР
- 0 XOR
Важно отметить, что XOR. Поэтому он не изменяет текущий номер во время OX ИЛИ не изменяет текущий номер.
- КСОР. Исходное значение равно A. Измененное значение по-прежнему равно A.
- О КСОР. Исходное значение равно O. Измененное значение равно A.
В заключение, XOR 0 вообще не должен обновлять наши карты.
Example:
We read the first element in our array which is 1.
1 XOR 2 gives us 3.
Since 3 is already in our counters then update num of counter.
Since 3 is already in our operations then update num of operations.
Counter {1:1, 2:1, 3:2}
Operations {1:0, 2:0, 3:1}
Как только мы закончим с петлями. Все, что нам нужно сделать, это найти максимальное количество встречаемости внутри нашего счетчика. Примечание: максимальное количество случаев может быть несколько. Из них мы должны найти минимальные операции. Таков был бы наш результат. Давайте закодируем это.
public static int[] findMax(int x, int[] arr) {
HashMap counter = new HashMap<>();
HashMap operations = new HashMap<>();
for(int num: arr) {
// count num of occurrence
counter.put(num, counter.getOrDefault(num, 0) + 1);
// initially there is 0 operation.
operations.put(num, 0);
}
for(int num: arr) {
// Special case where it does not give us a new number.
if(x == 0) {
break;
}
int xorResult = num ^ x;
// update counter and operations.
counter.put(xorResult, counter.getOrDefault(xorResult, 0) + 1);
operations.put(xorResult, operations.getOrDefault(xorResult, 0) + 1);
}
List list = new ArrayList<>();
int max = 1;
// Finding all numbers with greatest occurrences.
for(Map.Entry entry: counter.entrySet()){
if(max < entry.getValue()) {
max = entry.getValue();
list.clear();
list.add(entry.getKey());
} else if (max == entry.getValue()){
list.add(entry.getKey());
}
}
int minOperation = Integer.MAX_VALUE;
// Choose the lowest operations.
for(int num: list) {
minOperation = Math.min(minOperation, operations.get(num));
}
return new int[]{max, minOperation};
}
Сложность времени и пространства
Временная сложность O(n + n + n +(4 n)(n) Пространственная сложность O(n +(2 n)(n)
Оригинал: “https://dev.to/gangzhaorigeli/september-challenge-2021-division-3-xor-equal-l4b”