Маючи список цілих чисел, потрібно повернути розмір найбільшої комбінації цілих чисел, бітове AND яких більше за 0.
Отже, питання полягає в тому, щоб знайти розмір найбільшої комбінації цілих чисел, так щоб їх бітове AND давало число більше за 0. Ми знаємо одну річ про бітовий оператор AND; він обнуляє всі непарні біти.
Наприклад ->
5&17
00101
10001
— — — -
00001
Тепер наша мета змінюється: знайти найбільший список цілих чисел, у яких є хоча б один спільний біт. Добре, ми також знаємо, що максимальний розмір числа поміститься в 32-розрядне ціле. Чи можемо ми просто створити масив з 32 елементів для обчислення, скільки чисел у списку мають цей конкретний біт увімкненим? Це допоможе вирішити задачу, оскільки ми будемо знати, скільки чисел мають увімкнений цей біт.
Розглянемо приклад 8-розрядних чисел:
[16,17,71,62,12,24,14]
00010000 -> 16
00010001 -> 17
01000111 -> 71
00111110 -> 62
00001100 -> 12
00011000 -> 24
00001110 -> 14
set_bit_count_array = [0,0,0,0,0,0,0,0] // розмір масиву 8
Тепер порахуємо, скільки чисел мають увімкнений певний біт. Якщо взяти 16,
він увімкне 5-й біт, і так далі. Тепер масив стає таким:
[2,2,4,4,2,1]
Тепер ми знаємо, що є максимум 4 числа, які мають спільний біт, і якщо ми виконаємо
операції бітового AND для цих чисел, відповідь не буде 0, оскільки цей біт залишиться
увімкненим.
Це і відповідає на наше питання.
Код:
class Solution {
public:
int largestCombination(vector& candidates) {
vector bitsSetCount(32, 0);
int mx = 0;
for (int candidate: candidates) {
for (int i = 0; i < 32; i++) {
if ((candidate >> i) & 1)
bitsSetCount[i]++;
}
}
for (int bit: bitsSetCount) {
mx = max(bit, mx);
cout << bit << " ";
}
cout << "\n";
return mx;
}
};
Дякую.
Перекладено з: 2275. Largest Combination With Bitwise AND Greater Than Zero