문제 링크

• bit연산 아직 부족하다..

내 코드

못 풀었다.. (근데 더 간단한 방법이 생각이 나지 않음..)

class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        unordered_map<int, int> um;
        int answer{};
        for(int c : candidates) {
            for(auto& [k, v] : um) {
                if(k & c) {
                    if(um.count(k & c)) {
                        um[k & c] = max(um[k & c], v + 1);
                    }
                    else um.emplace(k & c, v + 1);

                    answer = max(answer, v + 1);
                }
            }
            if(um.count(c)) {
                um[c] = max(um[c], 1);
            }
            else um.emplace(c, 1);

            answer = max(answer, um[c]);
        }
        return answer;
    }
};

Solution

Approach 1: Using a Bit Count Array

• 45ms, 60.21MB
• Complexity
  • Time Complexity: $O(n \cdot b + b) = O(n)$
  • Space Complexity: $O(b) = O(1)$

class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        // Initialize a vector to store the count of each bit position.
        vector<int> bitCount(24, 0);
        for (int i = 0; i < 24; i++) {
            for (int num : candidates) {
                // Check if the i-th bit is set.
                if ((num & (1 << i)) != 0) {
                    bitCount[i]++;
                }
            }
        }
        // Return the maximum count.
        return *max_element(bitCount.begin(), bitCount.end());
    }
};

너무 어렵게 생각했다..

Approach 2: Direct Maximum Bit Count

• 41ms, 60.19MB
• Complexity
  • Time Complexity: $O(n \cdot b) = O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    int largestCombination(vector<int>& candidates) {
        int maxCount = 0;  // Variable to track the maximum count of set bits.
        for (int i = 0; i < 24; i++) {
            int count = 0;  // Count of numbers with the i-th bit set.
            for (int num : candidates) {
                if ((num & (1 << i)) != 0) {  // Check if the i-th bit is set.
                    count++;
                }
            }
            maxCount = max(maxCount, count);  // Update the maximum count.
        }
        return maxCount;
    }
};