C++ में बिटवाइज़ ORs के Subarrays

मान लीजिए कि हमारे पास गैर-ऋणात्मक पूर्णांकों की एक सरणी A है। प्रत्येक (सन्निहित) सबएरे के लिए बी =[ए [i], ए [i + 1], ..., ए [जे]] (i <=j के साथ) कहें, हम बिटवाइज या सभी तत्वों में से करेंगे बी, एक परिणाम प्राप्त करना ए [i] | ए[i+1] | ... | ए [जे]। हमें संभावित परिणामों की संख्या ज्ञात करनी है। (एक से अधिक बार आने वाले परिणाम अंतिम उत्तर में केवल एक बार गिने जाते हैं।)

तो अगर इनपुट [1,1,2] जैसा है, तो परिणाम 3 होगा क्योंकि उप-सरणी हैं [1], [1], [2], [1,1], [1,2], [1 1,2], तो परिणाम 1,1,2,1,3,3 होंगे, फिर तीन अलग-अलग परिणाम होंगे।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• दो सेट बनाएं रिट और curr2

• मेरे लिए 0 से लेकर सरणी के आकार तक

  • एक सेट curr1 बनाएं, इसमें A[i] डालें

  • curr2 में प्रत्येक तत्व ई के लिए -

    • curr1 में डालें (e OR A[i])

  • प्रत्येक तत्व ई curr1 के लिए

    • रिट में ई डालें

  • curr2 :=curr1

• वापसी का आकार

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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