3209. Number of Subarrays With AND Value of K

Posted on Edited on In

3209. Number of Subarrays With AND Value of K

Description

Given an array of integers nums and an integer k, return the number of subarrays of nums where the bitwise AND of the elements of the subarray equals k.

Example 1:

1
2
3
Input: nums = [1,1,1], k = 1

Output: 6

Explanation:

All subarrays contain only 1’s.

Example 2:

1
2
3
Input: nums = [1,1,2], k = 1

Output: 3

Explanation:

Subarrays having an AND value of 1 are: [1 ,1,2], [1,1 ,2], [1,1 ,2].

Example 3:

1
2
3
Input: nums = [1,2,3], k = 2

Output: 2

Explanation:

Subarrays having an AND value of 2 are: [1,2,3], [1,2,3 ].

Constraints:

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i], k <= 10^9

Hints/Notes

  • logTrick
  • Biweekly Contest 134

Solution

Language: C++

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
44
45
46
47
48
49
50
class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        long long res = 0;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int j = i - 1; j >= 0; j--) {
                if ((nums[j] & x) == nums[j]) {
                    break;
                }
                nums[j] &= x;
            }
            int left = findLeft(nums, 0, i, k);
            int right = findRight(nums, 0, i, k);
            res += right - left;
        }
        return res;
    }

    int findLeft(vector<int>& nums, int low, int high, int k) {
        int left = low, right = high;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == k) {
                right = mid - 1;
            } else if (nums[mid] < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    int findRight(vector<int>& nums, int low, int high, int k) {
        int left = low, right = high;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == k) {
                left = mid + 1;
            } else if (nums[mid] < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};