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.

For example: 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.

Another Example: 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 <= 10^5 1 <= nums[i] <= 10^9

## Longest Nice Subarray

This problem requires us to find the longest subarray in a given array of positive integers such that the bitwise AND of every pair of elements at different positions in the subarray is equal to 0.

### 1. Brute Force Approach

The most straightforward approach is to generate all possible subarrays and check if each subarray is "nice" according to the problem's definition. For each subarray, we iterate through all pairs of elements and compute their bitwise AND. If the AND of any pair is not 0, the subarray is not nice. We keep track of the longest nice subarray found so far.

```python
def is_nice_subarray(subarray):
    for i in range(len(subarray)):
        for j in range(i + 1, len(subarray)):
            if subarray[i] & subarray[j] != 0:
                return False
    return True

def longest_nice_subarray_brute_force(nums):
    max_len = 0
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            subarray = nums[i:j+1]
            if is_nice_subarray(subarray):
                max_len = max(max_len, len(subarray))
    return max_len

# Example usage
nums = [1, 3, 8, 48, 10]
print(longest_nice_subarray_brute_force(nums))  # Output: 3

2. Optimized Sliding Window Approach

We can optimize this by using a sliding window. We maintain a window (subarray) and keep track of the bitwise OR of all elements in the window. We expand the window to the right. If the bitwise AND of all pairs is 0, it means the bitwise OR of all elements should have at most one set bit for each bit position. If adding a new element to the window violates this condition, we shrink the window from the left until the condition is satisfied. The maximum length of the window during this process is the length of the longest nice subarray.

def longest_nice_subarray(nums):
    max_len = 0
    current_or = 0
    left = 0
    for right in range(len(nums)):
        while current_or & nums[right] != 0:
            current_or ^= nums[left]
            left += 1
        current_or |= nums[right]
        max_len = max(max_len, right - left + 1)
    return max_len

# Example usage
nums = [1, 3, 8, 48, 10]
print(longest_nice_subarray(nums))  # Output: 3

3. Big(O) Run-time Analysis

• Brute Force: The brute force approach generates all possible subarrays, which takes O(n^2) time. For each subarray, it checks if it is nice, which takes O(n^2) time in the worst case. Therefore, the overall time complexity is O(n^4).
• Sliding Window: The sliding window approach iterates through the array once with the right pointer. The left pointer can also move at most n times. The bitwise operations take constant time. Therefore, the overall time complexity is O(n).

4. Big(O) Space Usage Analysis

• Brute Force: The brute force approach uses constant extra space, so the space complexity is O(1).
• Sliding Window: The sliding window approach uses constant extra space to store current_or, left, and max_len, so the space complexity is O(1).

5. Edge Cases

• Empty Array: If the input array is empty, the longest nice subarray has length 0. The provided solutions handle this case correctly as the loops won't execute.
• Array with One Element: If the input array has only one element, the longest nice subarray has length 1. The solutions also handle this case correctly.
• Array with All Elements Equal to Zero: If all elements are zero, any subarray is a nice subarray. The algorithm will correctly return the length of the entire array.
• Large Numbers: The problem statement indicates numbers can be up to 10^9. The bitwise AND operation works correctly for these large numbers in both solutions.
• All elements cause the or to be non zero: The while condition in the sliding window takes care of removing elements on the left side until the bitwise AND of the current window becomes zero.