Problem

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:

  • E****ach element of the array belongs to exactly one subarray.
  • The sum of scores of the subarrays is the minimum possible.

Return themaximum number of subarrays in a split that satisfies the conditions above.

A subarray is a contiguous part of an array.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4

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 <= 10^5
  • 0 <= nums[i] <= 10^6

Solution

Method 1 – Greedy Bitwise AND Reset

Intuition

To minimize the sum of subarray scores, we want as many subarrays as possible with a score of 0. This happens whenever the running AND becomes zero, so we greedily start a new subarray each time this occurs.

Approach

  1. Initialize a running AND value to all bits set (e.g., -1 for 32-bit integers).
  2. Iterate through the array, updating the running AND with each element.
  3. When the running AND becomes zero, increment the subarray count and reset the running AND.
  4. Return the total count of subarrays formed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int maxSubarrays(vector<int>& nums) {
        int ans = 0, cur = -1;
        for (int x : nums) {
            cur &= x;
            if (cur == 0) {
                ++ans;
                cur = -1;
            }
        }
        return max(ans, 1);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func maxSubarrays(nums []int) int {
    ans, cur := 0, -1
    for _, x := range nums {
        cur &= x
        if cur == 0 {
            ans++
            cur = -1
        }
    }
    if ans == 0 {
        return 1
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int maxSubarrays(int[] nums) {
        int ans = 0, cur = -1;
        for (int x : nums) {
            cur &= x;
            if (cur == 0) {
                ++ans;
                cur = -1;
            }
        }
        return Math.max(ans, 1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun maxSubarrays(nums: IntArray): Int {
        var ans = 0
        var cur = -1
        for (x in nums) {
            cur = cur and x
            if (cur == 0) {
                ans++
                cur = -1
            }
        }
        return maxOf(ans, 1)
    }
}
1
2
3
4
5
6
7
8

def maxSubarrays(nums: list[int]) -> int:
    ans, cur = 0, -1
    for x in nums:
        cur &= x
        if cur == 0:
            ans += 1
            cur = -1
    return max(ans, 1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn max_subarrays(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut cur = -1;
        for x in nums {
            cur &= x;
            if cur == 0 {
                ans += 1;
                cur = -1;
            }
        }
        ans.max(1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    maxSubarrays(nums: number[]): number {
        let ans = 0, cur = -1;
        for (const x of nums) {
            cur &= x;
            if (cur === 0) {
                ans++;
                cur = -1;
            }
        }
        return Math.max(ans, 1);
    }
}

Complexity

  • ⏰ Time complexity: O(n) – Single pass through the array.
  • 🧺 Space complexity: O(1) – Only counters and a running AND value are used.