Approach #1: Brute force. [C++] [TEL]
int subarrayBitwiseORs1(vector<int>& A) {
int len = A.size();
set<int> ans;
for (int i = 0; i < len; ++i) {
for (int j = i; j < len; ++j) {
int temp = 0;
for (int k = i; k <= j; ++k) {
temp |= A[k];
}
ans.insert(temp);
}
}
return ans.size();
}
Approach #2: DP[ ][ ]. [C++] [TEL]
int subarrayBitwiseORs2(vector<int>& A) {
int len = A.size();
unordered_set<int> ans(begin(A), end(A));
vector<vector<int>> dp(len, vector<int>(len));
for (int l = 1; l <= len; ++l) {
for (int i = 0; i <= len - l; ++i) {
int j = i + l - 1;
if (l == 1) {
dp[i][j] = A[j];
continue;
}
dp[i][j] = dp[i][j-1] | A[j];
ans.insert(dp[i][j]);
}
}
return ans.size();
}
Approach #3: DP[ ]. [C++] [TEL]
int subarrayBitwiseORs3(vector<int>& A) {
int len = A.size();
unordered_set<int> ans(begin(A), end(A));
vector<int> dp(A);
for (int l = 2; l <= len; ++l) {
for (int i = 0; i <= len - l; ++i) {
ans.insert(dp[i] |= A[i+l-1]);
}
}
return ans.size();
}
Approach #4: DP + Bit. [C++]
int subarrayBitwiseORs(vector<int>& A) {
unordered_set<int> ans;
unordered_set<int> cur;
unordered_set<int> nxt;
for (int a : A) {
nxt.clear();
nxt.insert(a);
for (int c : cur) {
nxt.insert(c | a);
}
cur.swap(nxt);
ans.insert(begin(cur), end(cur));
}
return ans.size();
}
Approach #5: DP + Bit. [Java]
public int subarrayBitwiseORs(int[] A) {
Set<Integer> ans = new HashSet<>();
Set<Integer> cur = new HashSet<>();
for (int a : A) {
Set<Integer> nxt = new HashSet<>();
nxt.add(a);
for (int b : cur) {
nxt.add(b | a);
}
ans.addAll(nxt);
cur = nxt;
}
return ans.size();
}
Approach #6: DP + Bit. [Python]
class Solution(object):
def subarrayBitwiseORs(self, A):
"""
:type A: List[int]
:rtype: int
"""
cur = set()
ans = set() for a in A:
cur = {a | b for b in cur} | {a}
ans |= cur return len(ans)