You are given an array nums consisting of non-negative integers.
We define the score of subarray nums[l..r] such that l <= r as nums[l] AND nums[l + 1] AND ... AND nums[r] where AND is the bitwise AND operation.
Consider splitting the array into one or more subarrays such that the following conditions are satisfied:
Return the maximum number of subarrays in a split that satisfies the conditions above.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,0,2,0,1,2] Output: 3 Explanation: We can split the array into the following subarrays: - [1,0]. The score of this subarray is 1 AND 0 = 0. - [2,0]. The score of this subarray is 2 AND 0 = 0. - [1,2]. The score of this subarray is 1 AND 2 = 0. The sum of scores is 0 + 0 + 0 = 0, which is the minimum possible score that we can obtain. It can be shown that we cannot split the array into more than 3 subarrays with a total score of 0. So we return 3.
Example 2:
Input: nums = [5,7,1,3] Output: 1 Explanation: We can split the array into one subarray: [5,7,1,3] with a score of 1, which is the minimum possible score that we can obtain. It can be shown that we cannot split the array into more than 1 subarray with a total score of 1. So we return 1.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 106The key observation in #2871 Split Array Into Maximum Number of Subarrays is that the bitwise AND of numbers only decreases or stays the same as more elements are included. To maximize the number of subarrays, we should greedily create a split whenever the running AND becomes 0.
Start scanning the array while maintaining a running AND of the current segment. Each time you include a new element, update the running value using current &= nums[i]. If the result becomes 0, you have found a valid subarray whose AND is zero. At this point, increment the count and reset the running value to start forming the next segment.
This greedy strategy works because once the AND reaches zero, extending the segment further would only reduce the opportunity to create additional valid subarrays. The algorithm processes the array once, resulting in O(n) time complexity and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Running Bitwise AND | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
The minimum score will always be the bitwise <code>AND</code> of all elements of the array.
If the minimum score is not equal to <code>0</code>, the only possible split will be to keep all elements in one subarray.
Otherwise, all of the subarrays should have a score of <code>0</code>, we can greedily split the array while trying to make each subarray as small as possible.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems involving greedy decisions and bit manipulation frequently appear in FAANG-style interviews. This problem is a good practice example because it tests understanding of bitwise operations and greedy segmentation strategies.
No complex data structure is required. The problem can be solved with simple variables while iterating through the array and maintaining a running bitwise AND value.
The optimal approach uses a greedy strategy with a running bitwise AND. Traverse the array and keep updating the current AND value; whenever it becomes zero, form a subarray and reset the running value. This ensures the maximum number of valid splits.
Bitwise AND is monotonic decreasing as more numbers are added to a segment. Once the running AND becomes zero, extending the segment will not increase the result, so splitting immediately maximizes the number of subarrays.