Problem Description

You have an array nums containing non-negative integers. For any subarray nums[l..r] where l <= r, the score is calculated by performing bitwise AND on all elements: nums[l] AND nums[l+1] AND ... AND nums[r].

Your task is to split the entire array into one or more subarrays such that:

1. Every element belongs to exactly one subarray (no overlaps, no gaps)
2. The sum of all subarray scores is minimized

Among all possible splits that achieve the minimum sum of scores, return the maximum number of subarrays you can create.

For example, if you have an array [1, 0, 2, 0, 1, 2]:

• One possible split is the entire array as one subarray: score = 1 AND 0 AND 2 AND 0 AND 1 AND 2 = 0, giving sum = 0
• Another split could be [1, 0] and [2, 0, 1, 2]: scores are 0 and 0, giving sum = 0
• Or split as [1, 0], [2, 0], [1, 2]: scores are 0, 0, and 0, giving sum = 0

Since the minimum possible sum is 0, and we can achieve this with 3 subarrays, the answer would be 3.

The key insight is that the bitwise AND operation can only decrease or maintain values (never increase), and the minimum possible score for any subarray is 0. Therefore, we want to create as many subarrays with score 0 as possible to minimize the total sum while maximizing the number of splits.

Intuition

The key observation is that the bitwise AND operation has a special property: it can only decrease or stay the same as we include more numbers, never increase. This is because AND operation only keeps bits that are 1 in all numbers.

Since we want to minimize the sum of scores, the best possible score for any subarray is 0. Once we achieve a score of 0 for a subarray, continuing to add more elements to it won't make the score any better (it will remain 0). So whenever we reach a score of 0, we should immediately "cut" and start a new subarray.

Why does this greedy approach work? Consider what happens as we process elements from left to right:

• We start with the first element and keep adding elements while computing the running AND
• The moment this running AND becomes 0, we've found a subarray with the minimum possible score
• There's no benefit in extending this subarray further since the score can't get better than 0
• We reset and start looking for the next subarray with score 0

The special case to consider: what if we never encounter a score of 0 throughout the entire array? This means the AND of all elements is non-zero. In this case, we can't do better than keeping the entire array as one subarray, since splitting it would only increase the total sum (each split part would have a score ≥ the score of the whole).

This explains why the solution uses score = -1 as initialization (all bits set to 1 in two's complement), which acts as an identity element for AND operation. When we AND it with the first number, we get that number itself. The counter starts at 1 because we're counting the number of subarrays, and we always have at least one.

Learn more about Greedy patterns.

Solution Approach

The implementation uses a greedy approach with bitwise operations to find the maximum number of subarrays.

Variables Used:

• score: Tracks the running AND result of the current subarray being formed. Initialized to -1 (all bits set to 1), which acts as the identity element for AND operation.
• ans: Counts the number of subarrays. Starts at 1 since we always have at least one subarray.

Algorithm Steps:

1. Initialize variables: Set score = -1 and ans = 1. The -1 initialization ensures that when we AND it with the first number, we get that number itself (-1 & num = num).

2. Iterate through the array: For each element num in nums:

   • Perform bitwise AND: score &= num
   • This updates the score to be the AND of all elements in the current subarray being formed

3. Check for zero score: After each AND operation:

   • If score == 0, we've found a subarray with the minimum possible score
   • Reset score = -1 to start tracking a new subarray
   • Increment ans += 1 to count this new subarray we're about to start

4. Handle the final result:

   • If ans == 1, it means we never encountered a score of 0, so the entire array forms one subarray. Return 1.
   • Otherwise, return ans - 1. We subtract 1 because our counter was incremented one extra time when we found the last zero score, but there might not be any elements left to form another subarray.

Why the final adjustment? When we encounter score == 0, we increment ans anticipating a new subarray. However, if this happens at the end of the array, there are no more elements to form that next subarray. The condition ans == 1 checks if we never split the array at all (never found a zero score), in which case we return 1. Otherwise, we return ans - 1 to account for the over-counting.

Time Complexity: O(n) where n is the length of the array, as we traverse it once. Space Complexity: O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the array [3, 5, 1, 2] to illustrate the solution approach.

Initial Setup:

• score = -1 (all bits set, acts as identity for AND)
• ans = 1 (we always have at least one subarray)

Step-by-step Processing:

Iteration 1: Process element 3

• score = -1 & 3 = 3 (in binary: ...11111111 & 00000011 = 00000011)
• score ≠ 0, so continue
• Current subarray being formed: [3]

Iteration 2: Process element 5

• score = 3 & 5 = 1 (in binary: 00000011 & 00000101 = 00000001)
• score ≠ 0, so continue
• Current subarray being formed: [3, 5]

Iteration 3: Process element 1

• score = 1 & 1 = 1 (in binary: 00000001 & 00000001 = 00000001)
• score ≠ 0, so continue
• Current subarray being formed: [3, 5, 1]

Iteration 4: Process element 2

• score = 1 & 2 = 0 (in binary: 00000001 & 00000010 = 00000000)
• score == 0! We found a subarray with minimum score
• This means [3, 5, 1, 2] has AND score of 0
• Reset: score = -1
• Increment: ans = 2

Final Step:

• We've processed all elements
• ans = 2, which is greater than 1
• Return ans - 1 = 1

Why return 1? We found one complete subarray [3, 5, 1, 2] with score 0. When we hit score 0 at the last element, we incremented ans to 2 expecting to start a new subarray, but there were no more elements. So we correct by subtracting 1.

Verification: The only way to split this array with minimum sum is to keep it as one subarray (score = 0). Any other split would result in non-zero scores for the parts, giving a higher sum.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm iterates through the array exactly once with a single for loop, performing constant-time operations (bitwise AND operation, comparison, and variable assignments) for each element.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size, maintaining just two variables (score and ans) throughout the execution.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Initialization of the Score Variable

Problem: Initializing current_score to 0 instead of -1.

Many developers might intuitively initialize the score to 0, thinking it's the neutral element. However, for the bitwise AND operation:

• 0 & anything = 0, which would immediately give us a score of 0 regardless of the actual values
• -1 & num = num, which correctly starts our AND chain with the first number

Wrong Implementation:

current_score = 0  # WRONG!
for num in nums:
    current_score &= num  # This will always be 0

Correct Implementation:

current_score = -1  # Correct - acts as identity for AND
for num in nums:
    current_score &= num  # Properly accumulates the AND result

Pitfall 2: Off-by-One Error in Final Count

Problem: Forgetting to adjust the final count or adjusting it incorrectly.

The algorithm increments subarray_count when it finds a score of 0, anticipating the start of a new subarray. This creates two edge cases:

1. Never finding a zero score: The entire array is one subarray, but we initialized count to 1, so returning subarray_count directly is correct.

2. Finding zero score(s): We increment the count each time we find 0, but the last increment doesn't correspond to an actual new subarray if we've reached the end.

Wrong Implementation:

# Missing the adjustment
return subarray_count  # WRONG if we found any zeros!

Correct Implementation:

# Properly handle both cases
return 1 if subarray_count == 1 else subarray_count - 1

Pitfall 3: Misunderstanding When to Split

Problem: Trying to split at every element or using complex logic to determine split points.

The key insight is that we should only split when we achieve a score of 0, as this is the minimum possible value for any subarray. Splitting at any other point would either:

• Create subarrays with non-zero scores (increasing the total sum)
• Miss opportunities to create more subarrays with zero scores

Wrong Approach:

# Trying to split based on individual element values
if num == 0:  # WRONG - we need the AND result to be 0
    # split here

Correct Approach:

current_score &= num
if current_score == 0:  # Correct - split when AND result is 0
    # split here