leetcode-Longest-Nice-Subarray
Topic: array, bit manipulation, slide windown
Question
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] <= 109Analysis
example 1:
[1, 3, 8, 48, 10]
3 in bin: 0011
8 in bin: 1000
48d = 1100000
10d = 1010
0011 AND 1000 = 0
3, 8, 48 AND = 0
10 and 8 not = 0
so, if pair AND = 0
that pair have no common bit
so, we store a bit array to check the state of bit
and if, to better, we just need to store number of bit in that array instead.
oh no, it wrong.
so if we must store a array.
no, we can use bitwise operator & to check if a AND b == 0 or not
and OR for cumulative bit
x = 5
# 101
x |= 3
# 3 == 011
# 101 |= 011 = 111
print(x)
# 7 to search for longest (can use i, and j) for check all the begin and end
improve it by two pointer to decrease TC from O(n^2) to O(n)
and now, how to get rid of num of left from cumulative bit in slide windown
check that case: [011, 100]
now, culmulative bit: 111
we want it after left += 1, is 100
in XOR: 111 XOR 011 == 100
XOR parameter in python is ^=
Code
def longestNiceSubarray(self, nums: List[int]) -> int:
cumulative_bit = 0
ans = 0
left = 0
for right in range(len(nums)):
# when AND not ease
while cumulative_bit & nums[right] != 0: # right can not cumulative, increase left until it can ease, use XOR for get rid of it
cumulative_bit ^= nums[left]
left += 1
# until can AND
# use OR to cumulative it
cumulative_bit |= nums[right]
ans = max(ans, right - left + 1)
return ans