Sliding Window Technique - Part 6 (Bitwise)

In order to assure that a&b, b&c and a&c are all zero, keep track of the cumulative value of the bits for the 3 numbers. You can do it by using "|" operand (basically you're adding up all bits in a smart and linear way). The sliding window will be applied using this rule, but there is one caveat: when you move the left pointer, you'll have to remove it from the cumulative. You can do it by "&" the not of the element pointed by the left pointer. The code is down below, linear time, cheers, ACC.

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

Accepted

7,815

Submissions

19,027

public int LongestNiceSubarray(int[] nums)
{
    int left = 0;
    int right = 0;
    int cummulative = 0;
    int max = 0;

    while (right < nums.Length)
    {
        if (left == right)
        {
            cummulative = nums[left];
            max = Math.Max(max, 1);
            right++;
        }
        else
        {
            if ((cummulative & nums[right]) == 0)
            {
                cummulative |= nums[right];
                max = Math.Max(max, right - left + 1);
                right++;
            }
            else
            {
                cummulative &= (~nums[left]);
                left++;
            }
        }
    }

    return max;
}