main.go

// Source: https://leetcode.com/problems/longest-nice-subarray
// Title: Longest Nice Subarray
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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^5`
// - `1 <= nums[i] <= 10^9`
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

package main

// Note that (A or B) and C = (A and C) or (B and C)
// And [(A and C) or (B and C) = 0] iff. [A and C = 0] AND [B anc C = 0]
func longestNiceSubarray(nums []int) int {
	n := len(nums)
	res := 0
	for left := range n {
		curr := 0
		right := left
		for ; right < n; right++ {
			if curr&nums[right] == 0 {
				curr |= nums[right]
			} else {
				break
			}
		}
		res = max(res, right-left)
	}
	return res
}

// Note that (A or B) and C = (A and C) or (B and C)
// And [(A and C) or (B and C) = 0] iff. [A and C = 0] AND [B anc C = 0]
func longestNiceSubarray2(nums []int) int {
	n := len(nums)
	res := 0

	curr := 0
	right, left := 0, 0
	for right < n {
		if curr&nums[right] == 0 {
			curr |= nums[right]
		} else {
			curr = 0
			for left = right; left >= 0; left-- {
				if curr&nums[left] == 0 {
					curr |= nums[left]
				} else {
					break
				}
			}
			left++
		}
		right++
		res = max(res, right-left)
	}

	return res
}