leetcode-solution/Python/2401-longest-nice-subarray.py at main · hogan-tech/leetcode-solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# time complexity: O(n)
# space complexity: O(1)
from typing import List


class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        # for num in nums:
        #     print(f'{num:030b}')
        prefix = nums[0]
        left = 0
        result = 1
        for right in range(1, len(nums)):
            while prefix & nums[right] != 0:
                prefix ^= nums[left]
                left += 1
            prefix |= nums[right]
            result = max(result, right - left + 1)

        return result


'''
100111
100101
000010 -> 100111
000100


00 000101000000111101110110010111
01 101001010100110100101111100001
02 100100101000100111010000111101
03 011101101010100111011011110001
04 100100101100010100101001110111 l
05 000000000000000000000100001000 r
06 000000000000010000000000010000 r
07 000011000000000000000000000100
08 000000000000000000000000000001
09 000000000100000000000000000000
10 000000000000000100000000000000
11 000000000000000000001000100000
12 010000001000000000000000000000
13 001001000011000111110011100101
14 001101001110110001100100100111
15 101000011011000011000001100101
16 110010011010001000001111110001
17 101100110010010001011101100011
18 010011110001001010110101001101
19 101100000101001100001011100000
20 001111111101001101010110000000
'''
nums = [84139415, 693324769, 614626365, 497710833, 615598711, 264, 65552, 50331652, 1, 1048576, 16384,
        544, 270532608, 151813349, 221976871, 678178917, 845710321, 751376227, 331656525, 739558112, 267703680]
print(Solution().longestNiceSubarray(nums))

'''
 000001
 000011
 001000
 110000
 001010
'''
nums = [1, 3, 8, 48, 10]
print(Solution().longestNiceSubarray(nums))
'''
 000011
 000001
 000101
 001011
 001101
'''
nums = [3, 1, 5, 11, 13]
print(Solution().longestNiceSubarray(nums))