Given an array of integers nums and an integer k, return the number of subarrays of nums…
- User
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: Input: nums = [1,1,1], k = 1 Output: 6 Explanation: All subarrays contain only 1's.
Example 2: 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: 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
Write code as one function in C++.
- Assistant
To solve this problem efficiently, we'll use a two-pointer approach to iterate through the array and maintain a running bitwise AND for potential subarrays. The two-pointer technique will allow us to explore subarrays efficiently while updating the bitwise AND dynamically.
Here's a step-by-step explanation of the approach and the corresponding C++ code:
-
Initialize Pointers and Variables: We'll use two pointers,
startandend, withstartiterating over the start of the subarrays andendused to find possible end points. Also, initialize the running AND (runningAnd) and count of valid subarrays (count). -
Iterate Over the Array: We'll iterate over each element using the
endpointer. For each new element, check if the running AND still matcheskwhen extended up toend. -
Adjust the Start Pointer: If the current running AND doesn't equal
k, we need to move thestartpointer to attempt to regainkfor subsequent subarrays. -
Count Valid Subarrays: Each time the running AND equals
k, all subarrays starting from each position betweenstarttoendand ending atendare valid, count them.
Here is the C++ code for the solution:
#include <vector> #include <iostream> int countSubarraysWithBitwiseAND(std::vector<int>& nums, int k) { int n = nums.size(); int count = 0; int start = 0; while (start < n) { int runningAnd = nums[start]; if (runningAnd == k) count++; // Single element subarray check for (int end = start + 1; end < n; ++end) { runningAnd &= nums[end]; if (runningAnd == k) count++; else if (runningAnd < k) break; // Early stopping condition } ++start; // Move start to the next position } return count; } int main() { std::vector<int> nums1 = {1, 1, 1}; int k1 = 1; std::cout << countSubarraysWithBitwiseAND(nums1, k1) << std::endl; // Output: 6 std::vector<int> nums2 = {1, 1, 2}; int k2 = 1; std::cout << countSubarraysWithBitwiseAND(nums2, k2) << std::endl; // Output: 3 std::vector<int> nums3 = {1, 2, 3}; int k3 = 2; std::cout << countSubarraysWithBitwiseAND(nums3, k3) << std::endl; // Output: 2 return 0; }Explanation of the Code:
- Single Element Check: Firstly, check if the element itself forms a valid subarray of AND
k(e.g., a subarray of length 1). - Dynamic Running AND Calculation: As we grow the subarray from
starttoend, compute the running bitwise AND (runningAnd). If it becomes less thank(since numbers are non-negative), it cannot becomekagain, allowing for an early break. - Early Breaking Condition: If the
runningAnddrops belowk, further movingendonly decreases the bitwise AND further (sincenums[end]is non-negative), thus breaking early improves performance. - Incrementing Pointers: Progress the
startpointer to explore new subarrays starting from different indices.
This approach ensures we efficiently explore potential subarrays while maintaining the constraints of the problem.
-