[LeetCode] 2419. Longest Subarray With Maximum Bitwise AND

https://leetcode.com/problems/longest-subarray-with-maximum-bitwise-and/description/?envType=daily-question&envId=2024-09-14

leetcode - Longest Subarray With Maximum Bitwise AND

문제 유형 : 비트 연산, 비트마스킹, 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

You are given an integer array nums of size n.

Consider a non-empty subarray from nums that has the maximum possible bitwise AND.

• In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

 

n개의 정수가 담긴 정수 배열 nums가 주어진다.

모든 요소들을 비트 AND 연산한 값이  최대 크기인 부분배열의 크기를 구하시오.

 

풀이

AND연산은 요소가 많을수록 불리하다. 수의 비트가 다 가지고 있는 경우에만 보존되기에, 손해이다.

그래서, 최대는 보존일 뿐이다. 같은 크기의 수끼리 부분배열을 이뤄야 한다.

첫 순회에서는, 가장 큰 수를 찾는다.

두 번째 순회에서는 그 가장 큰 수들로만 이루어진 부분배열을 찾아서 최대 길이를 구한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int maxNum = 0;
        for(const auto &num : nums) {
            maxNum = max(maxNum, num);
        }

        int ans = 0;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == maxNum) {
                int len = 0;
                while(i < nums.size() && nums[i] == maxNum) {
                    i++;
                    len++;
                }
                ans = max(ans, len);
            }
        }
        return ans;
    }
};