2478. Longest Nice Subarray¶

Difficulty: Medium

2478. Longest Nice Subarray

Medium

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 <= 10⁵
1 <= nums[i] <= 10⁹

Solution¶

class Solution {
    public int longestNiceSubarray(int[] nums) {
        int n = nums.length;
        int low = 1, high = n;
        int ans = 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (ok(mid, nums)) {
                ans = mid;
                low = mid + 1;
            }
            else high = mid - 1;
        }
        return ans;
    }
    private boolean ok(int mid, int arr[]) {
        int n = arr.length;
        int freq[] = new int[33];
        for (int i = 0; i < mid; i++) {
            int current = arr[i];
            for (int j = 0; j < 32; j++) {
                int bit = ((current >> j) & 1);
                if (bit > 0) freq[j]++;
            }
        }
        boolean flag = true;
        for (int i = 0; i <= 32; i++) {
            if (freq[i] > 1) flag = false;
        }
        if (flag == true) return true;
        int start = 0;
        for (int i = mid; i < n; i++) {
            int last = arr[start], current = arr[i];
            flag = true;
            for (int j = 0; j < 32; j++) {
                int bit1 = ((last >> j) & 1);
                int bit2 = ((current >> j) & 1);
                if (bit1 > 0) freq[j]--;
                if (bit2 > 0) freq[j]++;
                if (freq[j] > 1) flag = false;
            }
            if (flag == true) return true;
            start++;
        }
        return false;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here