898. Bitwise ORs of Subarrays

We have an array arr of non-negative integers.

For every (contiguous) subarray sub = [arr[i], arr[i + 1], …, arr[j]] (with i <= j), we take the bitwise OR of all the elements in sub, obtaining a result arr[i] | arr[i + 1] | … | arr[j].

Return the number of possible results. Results that occur more than once are only counted once in the final answer

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> s, memo;
        for(auto& num : arr) {
            unordered_set<int> tmp;
            for(auto& mem : memo) {
                tmp.insert(mem | num);
            }
            memo = tmp;
            memo.insert(num);
            s.insert(begin(memo), end(memo));
        }
        return s.size();
    }
};

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> s;
        unordered_map<int, unordered_set<int>> checked;
        for(int i = 0; i < arr.size(); i++) {
            int num = arr[i];
            if(checked[i].count(num)) continue;
            checked[i].insert(num);
            s.insert(num);
            for (int j = i + 1; j < arr.size(); j++) {
                num |= arr[j];
                if(checked[j].count(num)) break;
                checked[j].insert(num);
                s.insert(num);
            }
        }

        return s.size();
    }
};