[LeetCode] Longest Nice Subarray

2401. Longest Nice Subarray

You are given an array nums consisting of positive integers.

We call a subarray of nums nice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to 0.

Return the length of the longest nice subarray.

A subarray is a contiguous part of an array.

Note that subarrays of length 1 are always considered nice.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int longestNiceSubarray(vector<int>& A) {
vector<int> freq(32);
int res = 0, l = 0, r = 0, n = A.size();
while(r < n) {
while(r < n and *max_element(begin(freq), end(freq)) <= 1) {
res = max(res, r - l);
for(int i = 0; i < 32; i++) {
if(A[r] & (1<<i)) freq[i]++;
}
r++;
}
if(*max_element(begin(freq), end(freq)) <= 1) res = max(res, r - l);
while(r < n and *max_element(begin(freq),end(freq)) > 1) {
for(int i = 0; i < 32; i++) {
if(A[l] & (1<<i)) freq[i]--;
}
l++;
}
}
return res;
}
};


Author: Song Hayoung
Link: https://songhayoung.github.io/2022/09/04/PS/LeetCode/longest-nice-subarray/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.