C++でのサブ配列のビットごとのOR

非負の整数の配列Aがあるとします。 B =[A [i]、A [i + 1]、...、A [j]]（i <=j）と言うすべての（連続する）サブ配列に対して、すべての要素のビットごとのORを実行します。 B、結果の取得A [i] | A [i + 1] | ... | A[j]。可能な結果の数を見つける必要があります。 （複数回発生した結果は、最終回答で1回だけカウントされます。）

したがって、入力が[1,1,2]の場合、サブ配列は[1]、[1]、[2]、[1,1]、[1,2]、[1]であるため、結果は3になります。 1,2]の場合、結果は1,1,2,1,3,3になり、3つの異なる結果が得られます。

これを解決するには、次の手順に従います-

• retとcurr2の2つのセットを作成します

• 0から配列のサイズまでの範囲のiの場合

  • セットcurr1を作成し、それにA[i]を挿入します

  • curr2の各要素eについて-

    • curr1に（e OR A [i]）を挿入します

  • 各要素についてecurr1

    • 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