Skip to content

3878. Count Good Subarrays

Description

You are given an integer array nums.

A subarray is called good if the bitwise OR of all its elements is equal to at least one element present in that subarray.

Return the number of good subarrays in nums.

Here, the bitwise OR of two integers a and b is denoted by a | b.

Β 

Example 1:

Input: nums = [4,2,3]

Output: 4

Explanation:

The subarrays of nums are:

Subarray Bitwise OR Present in Subarray
[4] 4 = 4 Yes
[2] 2 = 2 Yes
[3] 3 = 3 Yes
[4, 2] 4 | 2 = 6 No
[2, 3] 2 | 3 = 3 Yes
[4, 2, 3] 4 | 2 | 3 = 7 No

Thus, the good subarrays of nums are [4], [2], [3] and [2, 3]. Thus, the answer is 4.

Example 2:

Input: nums = [1,3,1]

Output: 6

Explanation:

Any subarray of nums containing 3 has bitwise OR equal to 3, and subarrays containing only 1 have bitwise OR equal to 1.

In both cases, the result is present in the subarray, so all subarrays are good, and the answer is 6.

Β 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109

Solutions

Solution 1: Monotonic Stack + Contribution Enumeration

We can enumerate each element \(\textit{nums}[i]\) as the bitwise OR result of a subarray, and count how many subarrays have a bitwise OR exactly equal to \(\textit{nums}[i]\).

If the bitwise OR of a subarray is \(\textit{nums}[i]\), then every element in the subarray must satisfy:

\[ \textit{nums}[k] \mid \textit{nums}[i] = \textit{nums}[i] \]

That is, every element in the subarray must be a subset of \(\textit{nums}[i]\) (in terms of bits). We can use a monotonic stack to find the left boundary \(l[i]\) and right boundary \(r[i]\) for each element \(\textit{nums}[i]\), such that all elements in the interval \((l[i], r[i])\) satisfy the above condition, while \(\textit{nums}[l[i]]\) and \(\textit{nums}[r[i]]\) do not. The number of subarrays with \(\textit{nums}[i]\) as the bitwise OR result is then \((i - l[i]) \cdot (r[i] - i)\).

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def countGoodSubarrays(self, nums: list[int]) -> int:
        n = len(nums)
        l = [-1] * n
        stk = []
        for i, x in enumerate(nums):
            while stk and nums[stk[-1]] < x and (nums[stk[-1]] | x) == x:
                stk.pop()
            l[i] = stk[-1] if stk else -1
            stk.append(i)
        r = [n] * n
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and (nums[stk[-1]] | nums[i]) == nums[i]:
                stk.pop()
            r[i] = stk[-1] if stk else n
            stk.append(i)
        return sum((i - l[i]) * (r[i] - i) for i in range(n))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public long countGoodSubarrays(int[] nums) {
        int n = nums.length;

        int[] l = new int[n];
        Arrays.fill(l, -1);
        Deque<Integer> stk = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            int x = nums[i];
            while (!stk.isEmpty() && nums[stk.peek()] < x && (nums[stk.peek()] | x) == x) {
                stk.pop();
            }
            l[i] = stk.isEmpty() ? -1 : stk.peek();
            stk.push(i);
        }

        int[] r = new int[n];
        Arrays.fill(r, n);
        stk.clear();

        for (int i = n - 1; i >= 0; i--) {
            while (!stk.isEmpty() && (nums[stk.peek()] | nums[i]) == nums[i]) {
                stk.pop();
            }
            r[i] = stk.isEmpty() ? n : stk.peek();
            stk.push(i);
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (long) (i - l[i]) * (r[i] - i);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    long long countGoodSubarrays(vector<int>& nums) {
        int n = nums.size();

        vector<int> l(n, -1);
        vector<int> stk;

        for (int i = 0; i < n; i++) {
            int x = nums[i];
            while (!stk.empty() && nums[stk.back()] < x && (nums[stk.back()] | x) == x) {
                stk.pop_back();
            }
            l[i] = stk.empty() ? -1 : stk.back();
            stk.push_back(i);
        }

        vector<int> r(n, n);
        stk.clear();

        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && (nums[stk.back()] | nums[i]) == nums[i]) {
                stk.pop_back();
            }
            r[i] = stk.empty() ? n : stk.back();
            stk.push_back(i);
        }

        long long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += 1LL * (i - l[i]) * (r[i] - i);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func countGoodSubarrays(nums []int) int64 {
    n := len(nums)

    l := make([]int, n)
    for i := range l {
        l[i] = -1
    }
    stk := []int{}

    for i, x := range nums {
        for len(stk) > 0 && nums[stk[len(stk)-1]] < x &&
            (nums[stk[len(stk)-1]]|x) == x {
            stk = stk[:len(stk)-1]
        }
        if len(stk) > 0 {
            l[i] = stk[len(stk)-1]
        }
        stk = append(stk, i)
    }

    r := make([]int, n)
    for i := range r {
        r[i] = n
    }
    stk = stk[:0]

    for i := n - 1; i >= 0; i-- {
        for len(stk) > 0 &&
            (nums[stk[len(stk)-1]]|nums[i]) == nums[i] {
            stk = stk[:len(stk)-1]
        }
        if len(stk) > 0 {
            r[i] = stk[len(stk)-1]
        }
        stk = append(stk, i)
    }

    var ans int64
    for i := 0; i < n; i++ {
        ans += int64(i-l[i]) * int64(r[i]-i)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function countGoodSubarrays(nums: number[]): number {
    const n = nums.length;

    const l = new Array(n).fill(-1);
    const stk: number[] = [];

    for (let i = 0; i < n; i++) {
        const x = nums[i];
        while (
            stk.length &&
            nums[stk[stk.length - 1]] < x &&
            (nums[stk[stk.length - 1]] | x) === x
        ) {
            stk.pop();
        }
        l[i] = stk.length ? stk[stk.length - 1] : -1;
        stk.push(i);
    }

    const r = new Array(n).fill(n);
    stk.length = 0;

    for (let i = n - 1; i >= 0; i--) {
        while (stk.length && (nums[stk[stk.length - 1]] | nums[i]) === nums[i]) {
            stk.pop();
        }
        r[i] = stk.length ? stk[stk.length - 1] : n;
        stk.push(i);
    }

    let ans = 0;
    for (let i = 0; i < n; i++) {
        ans += (i - l[i]) * (r[i] - i);
    }
    return ans;
}

Comments