[JAVA 문제 풀이] 409. Bitwise ORs of Subarrays

Bitwise ORs of Subarrays - LeetCode

Can you solve this real interview question? Bitwise ORs of Subarrays - Given an integer array arr, return the number of distinct bitwise ORs of all the non-empty subarrays of arr. The bitwise OR of a subarray is the bitwise OR of each integer in the subarray. The bitwise OR of a subarray of one integer is that integer. A subarray is a contiguous non-empty sequence of elements within an array.   Example 1: Input: arr = [0] Output: 1 Explanation: There is only one possible result: 0. Example 2: Input: arr = [1,1,2] Output: 3 Explanation: The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2]. These yield the results 1, 1, 2, 1, 3, 3. There are 3 unique values, so the answer is 3. Example 3: Input: arr = [1,2,4] Output: 6 Explanation: The possible results are 1, 2, 3, 4, 6, and 7.   Constraints: * 1 <= arr.length <= 5 * 104 * 0 <= arr[i] <= 109

https://leetcode.com/problems/bitwise-ors-of-subarrays/description/

정수 배열 'arr'이 주어졌을 때,
'arr'의 비어 있지 않은 모든 하위 배열의 비트 단위 OR의 수를 반환합니다.

서브어레이의 비트 단위 OR은 서브어레이의 각 정수의 비트 단위 OR입니다.
한 정수의 서브어레이의 비트 단위 OR은 해당 정수입니다.

서브어레이는 배열 내의 요소들의 연속적인 비어 있지 않은 시퀀스입니다.

제약 조건:
* 1 <= ar.length <= 5 * 10^4
* 0 <= arr[i] <= 109

내가 작성한 코드

import java.util.*;

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> answer = new HashSet<>(); // 최종 결과 집합
        Set<Integer> prev = new HashSet<>(); // 이전 위치까지의 OR 결과 집합

        for (int num : arr) {
            Set<Integer> cur = new HashSet<>();

            // 이전 OR 결과들에 대해 현재 수를 OR해서 추가
            for (int p : prev) {
                cur.add(p | num);
            }

            // 자기 자신도 추가 (새로운 subarray 시작)
            cur.add(num);

            // 이번에 나온 결과들을 전체 집합에 추가
            answer.addAll(cur);

            // 현재 OR 결과들을 다음 반복을 위해 저장
            prev = cur;
        }

        return answer.size();
    }
}