898. Bitwise ORs of Subarrays #

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. 1 <= A.length <= 50000
2. 0 <= A[i] <= 10^9

Problem Summary #

We have an array A of non-negative integers. For every (contiguous) subarray B = [A[i], A[i+1], …, A[j]] ( i <= j), we perform a bitwise OR operation on every element in B, obtaining the result A[i] | A[i+1] | … | A[j]. Return the number of possible results. (Results that occur multiple times are only counted once in the final answer.)

Solution Approach #

• Given an array, find the number of different results obtained by applying the | operation to all numbers within each subarray of this array.
• This problem can be considered as follows. First, consider how to obtain all subarrays. Taking [001, 011, 100, 110, 101] as an example, all subarray sets are as follows:

    [001]  
    [001 011] [011]  
    [001 011 100] [011 100] [100]  
    [001 011 100 110] [011 100 110] [100 110] [110]  
    [001 011 100 110 101] [011 100 110 101] [100 110 101] [110 101] [101]  

It can be seen that when traversing the original array from left to right, each newly arriving element is added in turn to the previously generated sets, and is also used as a standalone set. In this way, all subsets of the original array can be generated.

• Second, perform the | operation on all elements within the subsets of each row, obtaining:

    001  
    011 011  
    111 111 100  
    111 111 110 110  
    111 111 111 111 101  

• Third, deduplicate:

    001  
    011  
    111 100  
    111 110  
    111 101  

Since the number of binary bits does not exceed 32, each row here will contain at most 32 numbers. Therefore, the final time complexity will not exceed O(32 N), namely O(K * N). Finally, put all the numbers in each row into the final map for deduplication.

Code #

package leetcode

// Solution 1: optimized array version
func subarrayBitwiseORs(A []int) int {
	res, cur, isInMap := []int{}, []int{}, make(map[int]bool)
	cur = append(cur, 0)
	for _, v := range A {
		var cur2 []int
		for _, vv := range cur {
			tmp := v | vv
			if !inSlice(cur2, tmp) {
				cur2 = append(cur2, tmp)
			}
		}
		if !inSlice(cur2, v) {
			cur2 = append(cur2, v)
		}
		cur = cur2
		for _, vv := range cur {
			if _, ok := isInMap[vv]; !ok {
				isInMap[vv] = true
				res = append(res, vv)
			}
		}
	}
	return len(res)
}

func inSlice(A []int, T int) bool {
	for _, v := range A {
		if v == T {
			return true
		}
	}
	return false
}

// Solution 2: map version
func subarrayBitwiseORs1(A []int) int {
	res, t := map[int]bool{}, map[int]bool{}
	for _, num := range A {
		r := map[int]bool{}
		r[num] = true
		for n := range t {
			r[(num | n)] = true
		}
		t = r
		for n := range t {
			res[n] = true
		}
	}
	return len(res)
}