[LeetCode] 2275. Largest Combination With Bitwise AND Greater Than Zero

https://leetcode.com/problems/largest-combination-with-bitwise-and-greater-than-zero/description/?envType=daily-question&envId=2024-11-07

leetcode - Largest Combination With Bitwise AND Greater Than Zero

문제 유형: 비트마스킹, 비트 조작

문제 난이도: Medium

 

문제

The bitwise AND of an array nums is the bitwise AND of all integers in nums.

• For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.
• Also, for nums = [7], the bitwise AND is 7.

You are given an array of positive integers candidates. Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.

Return the size of the largest combination of candidates with a bitwise AND greater than 0.

 

배열의 bitwise AND는 정수 배열 nums의 모든 요소를 bitwise AND연산한 값이다.

candidates배열이 주어진다. 이 배열의 요소들을 최대 1개씩 골라 조합하여 가장 큰 조합을 만드시오.

단, 그 조합의 bitwise AND는 0보다 커야 합니다.

 

풀이

수의 제한에는, 10^7이라 되어있다.

즉, 24비트 이내의 수로 표현될 수 있다.

그리고, 배열의 bitwise AND를 했을 때 0보다 크려면, 그 값은 적어도 하나 이상의 비트가 1이어야 하고, 즉, 각 요소들은 그 하나라도 공통된 자릿수의 1을 가지고 있어야 한다.

 

0비트부터 23번째비트까지 한 번씩 만들어서(4비트의 예시를 들자면: 0001, 0010, 0100, 1000)

배열의 숫자들과 비교하여 그 비트를 가지고 있다면, 개수를 누적한다.

이렇게 누적된 자릿수별 비트들 중, 최대값을 반환한다.

 

코드

C++

class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        int n = candidates.size();
        
        int ans = 0;
        for(int b = 0; b < 24; ++b) {
            int x = 0;
            for(int i = 0; i < n; ++i) {
                if(candidates[i] & (1 << b)) x++;
            }
            ans = max(ans, x);
        }

        return ans;
    }
};