Problem
We have an array A
of non-negative integers.
For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]]
(with i <= j
), we take the bitwise OR of all the elements in B
, obtaining a result A[i] | A[i+1] | ... | A[j]
.
Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)
Example 1:
Input: [0] Output: 1 Explanation: There is only one possible result: 0.
Example 2:
Input: [1,1,2] Output: 3 Explanation: The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2]. These yield the results 1, 1, 2, 1, 3, 3. There are 3 unique values, so the answer is 3.
Example 3:
Input: [1,2,4] Output: 6 Explanation: The possible results are 1, 2, 3, 4, 6, and 7.
Note:
1 <= A.length <= 50000
0 <= A[i] <= 10^9
Solution 1: DP (TLE)
dp[i][j] := A[i] | A[i + 1] | … | A[j]
dp[i][j] = dp[i][j – 1] | A[j]
ans = len(set(dp))
Time complexity: O(n^2)
Space complexity: O(n^2) -> O(n)
C++ SC O(n^2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: TLE (73/83 passed). class Solution { public: int subarrayBitwiseORs(vector<int>& A) { int n = A.size(); vector<vector<int>> dp(n, vector<int>(n)); unordered_set<int> ans(begin(A), end(A)); for (int l = 1; l <= n; ++l) for (int i = 0; i <= n - l; ++i) { int j = i + l - 1; if (l == 1) { dp[i][j] = A[i]; continue; } dp[i][j] = dp[i][j - 1] | A[j]; ans.insert(dp[i][j]); } return ans.size(); } }; |
C++ SC O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua // Running time: TLE (75/83 passed) class Solution { public: int subarrayBitwiseORs(vector<int>& A) { int n = A.size(); vector<int> dp(A); unordered_set<int> ans(begin(A), end(A)); for (int l = 2; l <= n; ++l) for (int i = 0; i <= n - l; ++i) ans.insert(dp[i] |= A[i + l - 1]); return ans.size(); } }; |
Solution 2: DP opted
dp[i] := {A[i], A[i] | A[i – 1], A[i] | A[i – 1] | A[i – 2], … , A[i] | A[i – 1] | … | A[0]}, bitwise ors of all subarrays end with A[i].
|dp[i]| <= 32
Proof: all the elements (in the order of above sequence) in dp[i] are monotonically increasing by flipping 0 bits to 1 from A[i].
There are at most 32 0s in A[i]. Thus the size of the set is <= 32.
证明: dp[i] = {A[i], A[i] | A[i – 1], A[i] | A[i – 1] | A[i – 2], … , A[i] | A[i – 1] | … | A[0]},这个序列单调递增,通过把A[i]中的0变成1。A[i]最多有32个0。所以这个集合的大小 <= 32。
e.g. 举例:Worst Case 最坏情况 A = [8, 4, 2, 1, 0] A[i] = 2^(n-i)。
A[5] = 0,dp[5] = {0, 0 | 1, 0 | 1 | 2, 0 | 1 | 2 | 4, 0 | 1 | 2 | 4 | 8} = {0, 1, 3, 7, 15}.
Time complexity: O(n*log(max(A))) < O(32n)
Space complexity: O(n*log(max(A)) < O(32n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua // Running time: 456 ms class Solution { public: 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 b : cur) { nxt.insert(a | b); } cur.swap(nxt); ans.insert(begin(cur), end(cur)); } return ans.size(); } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 434 ms class Solution { 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(a | b); ans.addAll(nxt); cur = nxt; } return ans.size(); } } |
Python3
1 2 3 4 5 6 7 8 9 10 |
# Author: Huahua # Running time: 812 ms class Solution: def subarrayBitwiseORs(self, A): cur = set() ans = set() for a in A: cur = {a | b for b in cur} | {a} ans |= cur return len(ans) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment