[LeetCode] 2401. Longest Nice Subarray (Python)

 

 

난이도: Medium

Problem Description

---

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.

 

 

Problem Example

---

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

---

class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        answer = 1

        for right in range(len(nums)):
            now = nums[right]
            left = right -1
            while left >= 0 and now & nums[left] == 0:
                now |= nums[left]
                left -= 1
            
            answer = max(answer, right - left)

        return answer

 

약간 bruteforce 방식으로 푼 느낌이 없지 않아 있다..

 

right를 키워가며 left를 right-1로 설정하고 left를 -1씩 하면서 nums의 요소들을 AND 연산 했을 때 0이 나오지는 지 확인했다.

 

즉, 현재까지의 부분 배열 내 모든 숫자와 새로 추가된 숫자가 비트적으로 겹치지 않는지 검사하였다.

 

만약 AND 연산 시 값이 0이 아니면 반복문을 종료하고 max(answer, right-left)를 통해 최대 길이를 구할 수 있었다.

 

 

⚙️ Runtime & Memory

---

 

 

---

문제: 2401. Longest Nice Subarray

 

깃허브: github

algorithmPractice/LeetCode/2478-longest-nice-subarray at main · laewonJeong/algorithmPractice