C++에서 부분배열의 비트 OR

음이 아닌 정수의 배열 A가 있다고 가정합니다. 모든 (인접한) 하위 배열에 대해 B =[A[i], A[i+1], ..., A[j]] (i <=j 사용)에 대해 모든 요소의 비트 OR을 수행합니다. B, 결과 얻기 A[i] | A[i+1] | ... | 에이[제]. 가능한 결과의 수를 찾아야 합니다. (두 번 이상 발생한 결과는 최종 답변에서 한 번만 계산됩니다.)

따라서 입력이 [1,1,2]와 같으면 하위 배열이 [1], [1], [2], [1,1], [1,2], [1, 1,2], 결과는 1,1,2,1,3,3이 되고 세 가지 다른 결과가 나타납니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 두 세트 ret 및 curr2 생성

• 범위 0에서 배열 크기까지의 i에 대해

  • 세트 curr1을 만들고 A[i]를 삽입하십시오.

  • curr2의 각 요소 e에 대해 -

    • curr1에 (e OR A[i]) 삽입

  • 각 요소 e curr1

    • ret에 e 삽입

  • curr2 :=curr1

• ret의 반환 크기

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int subarrayBitwiseORs(vector<int>& A) {
      unordered_set <int> ret;
      unordered_set <int> curr2;
      for(int i = 0; i < A.size(); i++){
         unordered_set <int> curr1;
         curr1.insert(A[i]);
         unordered_set<int>::iterator it = curr2.begin();
         while(it != curr2.end()){
            curr1.insert(*it | A[i]);
            it++;
         }
         it = curr1.begin();
         while(it != curr1.end()){
            ret.insert(*it);
            it++;
         }
         curr2 = curr1;
      }
      return ret.size();
   }
};
main(){
   vector<int> v = {1,1,2};
   Solution ob;
   cout << (ob.subarrayBitwiseORs(v));
}

입력

[1,1,2]

출력

3