C++ में सबएरे के बिटवाइज OR (Bitwise ORs of Subarrays)

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

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

समाधान दृष्टिकोण

1. दो सेट ret और curr2 बनाएं

2. प्रत्येक तत्व A[i] के लिए: curr1 में A[i] डालें

3. curr2 के प्रत्येक तत्व e के लिए: curr1 में (e | A[i]) डालें

4. curr1 के सभी तत्व ret में डालें

5. curr2 := curr1 अपडेट करें

6. ret का आकार लौटाएं

C++ कार्यान्वयन

#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]); 
            for(auto it = curr2.begin(); it != curr2.end(); it++){ 
                curr1.insert(*it | A[i]); 
            } 
            for(auto it = curr1.begin(); it != curr1.end(); it++){ 
                ret.insert(*it); 
            } 
            curr2 = curr1; 
        } 
        return ret.size(); 
    } 
}; 

int main(){ 
    vector<int> v = {1,1,2}; 
    Solution ob; 
    cout << (ob.subarrayBitwiseORs(v)); 
    return 0; 
}

इनपुट

[1,1,2]

आउटपुट

3