Question

2401. Longest Nice Subarray

中文文档

Description

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.

 

Example 1:

Input: nums = [1,3,8,48,10]
Output: 3
Explanation: The longest nice subarray is [3,8,48]. This subarray satisfies the conditions:
- 3 AND 8 = 0.
- 3 AND 48 = 0.
- 8 AND 48 = 0.
It can be proven that no longer nice subarray can be obtained, so we return 3.

Example 2:

Input: nums = [3,1,5,11,13]
Output: 1
Explanation: The length of the longest nice subarray is 1. Any subarray of length 1 can be chosen.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Solutions

Solution 1: Two Pointers

We define a variable $mask$ to record the bitwise OR result of the elements in the current subarray, initially $mask = 0$. Also, we use two pointers $j$ and $i$ to point to the left and right endpoints of the current subarray, initially $i = j = 0$.

Next, we traverse the array $nums$ from left to right. For each element $x$ we encounter:

We perform a bitwise AND operation between it and $mask$. If the result is not $0$, it means that $x$ and at least one element in $mask$ have a binary representation where a certain bit is $1$, and the corresponding bit in the other element's binary representation is $0$. Such pairs of elements cannot satisfy the problem's requirements, so we need to move $j$ to the right until the bitwise AND result of $x$ and $mask$ is $0$.

At this point, we have found a subarray that satisfies the problem's requirements. Its length is $i - j + 1$. We compare it with the length of the current longest elegant subarray. If it is longer than the current longest elegant subarray, we update the length of the longest elegant subarray.

Then we perform a bitwise OR operation between $mask$ and $x$, and continue to the next element.

Finally, the length of the longest elegant subarray we obtain is the answer.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $nums$.

class Solution:
  def longestNiceSubarray(self, nums: List[int]) -> int:
    ans = j = mask = 0
    for i, x in enumerate(nums):
      while mask & x:
        mask ^= nums[j]
        j += 1
      ans = max(ans, i - j + 1)
      mask |= x
    return ans

class Solution {
  public int longestNiceSubarray(int[] nums) {
    int ans = 0, mask = 0;
    for (int i = 0, j = 0; i < nums.length; ++i) {
      while ((mask & nums[i]) != 0) {
        mask ^= nums[j++];
      }
      ans = Math.max(ans, i - j + 1);
      mask |= nums[i];
    }
    return ans;
  }
}

class Solution {
public:
  int longestNiceSubarray(vector<int>& nums) {
    int ans = 0, mask = 0;
    for (int i = 0, j = 0; i < nums.size(); ++i) {
      while (mask & nums[i]) {
        mask ^= nums[j++];
      }
      ans = max(ans, i - j + 1);
      mask |= nums[i];
    }
    return ans;
  }
};

func longestNiceSubarray(nums []int) (ans int) {
  mask, j := 0, 0
  for i, x := range nums {
    for ; mask&x != 0; j++ {
      mask ^= nums[j]
    }
    if k := i - j + 1; ans < k {
      ans = k
    }
    mask |= x
  }
  return
}

function longestNiceSubarray(nums: number[]): number {
  let mask = 0;
  let ans = 0;
  for (let i = 0, j = 0; i < nums.length; ++i) {
    while ((mask & nums[i]) !== 0) {
      mask ^= nums[j++];
    }
    ans = Math.max(ans, i - j + 1);
    mask |= nums[i];
  }
  return ans;
}