Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2401.html

2401. Longest Nice Subarray

  • Difficulty: Medium.
  • Related Topics: Array, Bit Manipulation, Sliding Window.
  • Similar Questions: Longest Substring Without Repeating Characters, Bitwise AND of Numbers Range, Bitwise ORs of Subarrays, Fruit Into Baskets, Max Consecutive Ones III, Get Equal Substrings Within Budget, Frequency of the Most Frequent Element, Longest Substring Of All Vowels in Order, Maximize the Confusion of an Exam.

Problem

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

Solution (Java, C++, Python)

  • class Solution {
        public int longestNiceSubarray(int[] nums) {
            int maxCount = 1;
            int count = 1;
    
            List<Integer> list = new ArrayList<>();
    
            for (int i = 0; i < nums.length - 1; i++) {
                list.clear();
                list.add(nums[i]);
                count = 1;
                for (int j = i + 1; j < nums.length; j++) {
                    if ((nums[i] & nums[j]) == 0) {
                        list.add(nums[j]);
                    } else
                        break;
                }
    
                boolean bool = true;
                    if (list.size() != 1) {
                    for (int i1 = 1; i1 < list.size(); i1++) {
                        for (int j = 0; j < i1; j++) {
                            if (i1!=j&&(list.get(i1) & list.get(j)) != 0) {
                                bool = false;
                                break;
                            }
                        }
                        if (bool)
                            count++;
                        else
                            break;
                    }
                    
                    if (maxCount<count)
                        maxCount = count;
                }
            }
            return maxCount;
        }
    }
    
    ############
    
    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:
        def longestNiceSubarray(self, nums: List[int]) -> int:
            ans = j = t = 0
            for i, v in enumerate(nums):
                while t & v:
                    t ^= nums[j]
                    j += 1
                t |= v
                ans = max(ans, i - j + 1)
            return ans
    
    ############
    
    # 2401. Longest Nice Subarray
    # https://leetcode.com/problems/longest-nice-subarray/
    
    class Solution:
        def longestNiceSubarray(self, nums: List[int]) -> int:
            n = len(nums)
            res = 1
            i = mask = 0
            
            for j, x in enumerate(nums):
                while mask & x != 0:
                    mask ^= (nums[i])
                    i += 1
                    
                mask |= x
                res = max(res, j - i + 1)
            
            return res
    
    
  • 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;
    }
    
    

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions