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: 1Explanation:
There is only one possible result: 0.
Example 2:
Input: [1,1,2]Output: 3Explanation:
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: 6Explanation:
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).
classSolution{
public:
intsubarrayBitwiseORs(vector<int>& A) {
int n = A.size();
vector<vector<int>>dp(n,vector<int>(n));
unordered_set<int>ans(begin(A),end(A));
for(intl=1;l<=n;++l)
for(inti=0;i<=n-l;++i){
intj=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]);
}
returnans.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)
classSolution{
public:
intsubarrayBitwiseORs(vector<int>& A) {
int n = A.size();
vector<int>dp(A);
unordered_set<int>ans(begin(A),end(A));
for(intl=2;l<=n;++l)
for(inti=0;i<=n-l;++i)
ans.insert(dp[i]|=A[i+l-1]);
returnans.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.
Given a positive integer N, find and return the longest distance between two consecutive 1’s in the binary representation of N.
If there aren’t two consecutive 1’s, return 0.
Example 1:
Input: 22Output: 2
Explanation:
22 in binary is 0b10110.
In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
The first consecutive pair of 1's have distance 2.
The second consecutive pair of 1's have distance 1.
The answer is the largest of these two distances, which is 2.
Example 2:
Input: 5Output: 2Explanation:
5 in binary is 0b101.
Example 3:
Input: 6Output: 1Explanation:
6 in binary is 0b110.
Example 4:
Input: 8Output: 0Explanation:
8 in binary is 0b1000.
There aren't any consecutive pairs of 1's in the binary representation of 8, so we return 0.\
According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.
Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
We are given non-negative integers nums[i] which are written on a chalkboard. Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first. If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become 0, then that player loses. (Also, we’ll say the bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.)
Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.
Return True if and only if Alice wins the game, assuming both players play optimally.
Example:Input: nums = [1, 1, 2]
Output: false
Explanation:
Alice has two choices: erase 1 or erase 2.
If she erases 1, the nums array becomes [1, 2]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 2 = 3. Now Bob can remove any element he wants, because Alice will be the one to erase the last element and she will lose.
If Alice erases 2 first, now nums becomes [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.