We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Split Array Into Maximum Number of Subarrays

Number: 3080

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array nums of non-negative integers, split it into one or more contiguous subarrays so that every element is in exactly one subarray. Define the score of a subarray as the bitwise AND of all of its elements. The objective is to minimize the total score (i.e. the sum of the scores of the subarrays) while maximizing the number of subarrays in the split. Return the maximum number of subarrays that can be formed under this condition.

Key Insights

  • The minimal possible score overall is the bitwise AND of the entire array.
  • For any split to achieve the minimum sum, each subarray must have a bitwise AND equal to the global AND.
  • A greedy approach is viable: iterate over the array, maintaining a running AND; whenever the running AND equals the global AND, a valid subarray is complete.
  • Reset the running AND and continue to form the next valid subarray.
  • This method naturally maximizes the number of subarrays.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array (each element is processed once). Space Complexity: O(1), constant extra space is used.

Solution

First, compute the global AND of the entire array. This value is the lower bound for the total sum, since any valid split must have each subarray's AND equal to at least this value. Then, iterate through the arraymaintaining a running AND of the current subarray. When the running AND becomes equal to the global AND, a valid subarray is identified; increment your count and reset the running AND for the next segment. Continue this until the end of the array. The count will be the maximum number of subarrays achieving the minimal sum, as each split is as short as possible while still satisfying the condition.

Code Solutions

# Python solution with detailed comments

def maxSubarraysSplit(nums):
    # Compute the global AND
    global_and = nums[0]
    for num in nums[1:]:
        global_and &= num
    
    # Initialize count for valid subarrays and a variable for current segment AND
    subarray_count = 0
    current_and = -1  # Using -1 because in bitwise operations, -1 has all bits set
    
    # Iterate over the array
    for num in nums:
        current_and &= num  # Update running AND for the current subarray
        # When the running AND equals the global AND, we have a valid segment.
        if current_and == global_and:
            subarray_count += 1  # Increase the count of valid segments
            current_and = -1     # Reset current AND for the next subarray
    return subarray_count

# Example usage:
print(maxSubarraysSplit([1,0,2,0,1,2]))  # Output: 3
print(maxSubarraysSplit([5,7,1,3]))        # Output: 1
← Back to All Questions