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] <= 106Problem Overview: You are given an integer array and need to split it into the maximum number of non‑empty subarrays such that the bitwise AND of every subarray equals 0. The goal is to maximize the number of valid splits while scanning the array only once.
Approach 1: Divide at Zero AND Positions (Greedy Scan) (Time: O(n), Space: O(1))
The key observation is that the bitwise AND of numbers can only decrease as you add more elements to a subarray. Once the running AND becomes 0, adding more elements cannot increase it back to a non‑zero value. That means the best strategy is to immediately split the array at that point to maximize the number of segments. Iterate through the array while maintaining a running AND value. Every time the running AND becomes 0, increment the subarray count and reset the running value for the next segment. This greedy strategy guarantees the maximum number of valid subarrays because delaying a split never produces more segments later. The solution runs in linear time and constant space, making it optimal for large inputs. This technique relies on properties of bit manipulation combined with a simple greedy decision at each step.
Approach 2: Running AND Reset Strategy (Without Explicit Zero Counting) (Time: O(n), Space: O(1))
Another way to implement the same idea is to continuously maintain a cumulative AND while iterating through the array. Start with the current value initialized to all bits set (or simply the first element). For every element, update current &= nums[i]. When the value becomes 0, a valid subarray has been formed, so increment the result and reset the running AND to begin evaluating the next segment independently. If the entire traversal never produces a zero AND, the whole array must remain as a single subarray. This approach avoids explicitly tracking positions where zero occurs and instead relies on the natural behavior of cumulative AND operations. It is still an O(n) scan over the array with constant extra memory.
Recommended for interviews: Interviewers expect the greedy running‑AND solution. A brute force approach would check every possible split and compute subarray AND values, which quickly becomes inefficient. Demonstrating the insight that AND values only decrease and that splitting immediately at zero maximizes the segment count shows strong understanding of greedy reasoning and bitwise behavior.
The key observation is that any subarray that contains a zero will have a score of zero. Hence, the goal is to maximize the number of subarrays with scores equal to zero by dividing the array at zero positions. The number of zero elements in the array determines the maximum number of subarrays that can be formed with a sum of scores equal to zero.
This C solution iterates through the array and counts the number of zeros. Since subarrays are split at positions where zeros occur, the number of zeros directly corresponds to the maximum number of subarrays with zero scores. If no zeros are found, the whole array is one subarray.
Time Complexity: O(n), where n is the number of elements in the array
Space Complexity: O(1) because we use a constant amount of extra space.
In certain cases, especially for educational purposes, you may choose to approach the problem by iterating through the array manually maintaining a running state if the current segment contains a zero or not, indirectly counting subarrays that produce zero scores.
This C solution involves checking when a new zero streak starts by marking the start with a boolean flag `foundZero`. This is checked each time a zero is encountered, and increments a counter only once per streak.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1) due to use of constant space regardless of input size.
We initialize a variable score to record the score of the current subarray, and set score=-1 initially. Then we traverse the array, for each element num, we perform a bitwise AND operation between score and num, and assign the result to score. If score=0, it means the score of the current subarray is 0, so we can split the current subarray and reset score to -1. Finally, we return the number of split subarrays.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Divide at Zero Positions | Time Complexity: O(n), where n is the number of elements in the array |
| Alternative Way without Direct Zero Count | Time Complexity: O(n), where n is the number of elements in the array. |
| Greedy + Bitwise Operation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray AND Checking | O(n²) | O(1) | Useful only for understanding the problem or very small arrays |
| Divide at Zero AND Positions (Greedy) | O(n) | O(1) | Optimal solution for interviews and production constraints |
| Running AND Reset Strategy | O(n) | O(1) | Clean implementation when scanning once and resetting after each valid segment |
2871. Split Array Into Maximum Number of Subarrays 🔥 || Bit Manipulation 👏🏻 • Ayush Rao • 1,369 views views
Watch 9 more video solutions →Practice Split Array Into Maximum Number of Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor