Split Array Into Maximum Number of Subarrays

Split Array Into Maximum Number of Subarrays - 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:

Each element of the array belongs to exactly one subarray.
The sum of scores of the subarrays is the minimum possible.

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

A subarray is a contiguous part of an array.

Input & Output

Example 1 — Basic Split

$ Input: nums = [1,0,2,0,1]

› Output: 4

💡 Note: We can split into [1], [0], [2,0], [1]. Scores are 1, 0, 0, 1 with sum = 2. This is minimum possible, and we have 4 subarrays.

Example 2 — Single Subarray

$ Input: nums = [5,7,1,3]

› Output: 1

💡 Note: The entire array AND is 5&7&1&3 = 1 > 0. To minimize sum, we must keep as one subarray [5,7,1,3] with score 1.

Example 3 — All Zeros

$ Input: nums = [0,0,0]

› Output: 3

💡 Note: We can split into [0], [0], [0]. Each subarray has score 0, sum = 0 (minimum), with 3 subarrays maximum.

Constraints

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,0,2,0,1] needs to be split optimally

Process

Find minimum sum, then split greedily

Output

Maximum 4 subarrays with minimum sum

Key Takeaway

🎯 Key Insight: AND operations only decrease values, so split greedily when reaching zero

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is that AND operations only decrease values, so we want to split greedily when the running AND becomes zero to minimize the sum while maximizing subarrays. Best approach is greedy splitting. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Partitions	O(2ⁿ × n²)	O(n)	Generate all possible partitions and find those with minimum sum of scores
Greedy - Split When AND Becomes Zero	O(n)	O(1)	Greedily split whenever the running AND becomes zero or we've achieved minimum possible sum

Brute Force - Try All Partitions — Algorithm Steps

Generate all possible partitions using recursion
Calculate AND score for each subarray in partition
Find minimum possible sum of scores
Count maximum subarrays among minimum sum partitions

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Partitions

Try every way to split array into subarrays

Calculate Scores

Compute AND for each subarray in partition

Find Minimum

Track partitions with minimum sum of scores

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int minSum = INT_MAX;
int maxSubarrays = 0;

void backtrack(int* nums, int n, int index, int* partition, int partitionSize, int currentSum) {
    if (index == n) {
        if (currentSum < minSum) {
            minSum = currentSum;
            maxSubarrays = partitionSize;
        } else if (currentSum == minSum) {
            if (partitionSize > maxSubarrays) {
                maxSubarrays = partitionSize;
            }
        }
        return;
    }
    
    // Try all possible end positions for next subarray
    for (int end = index; end < n; end++) {
        // Calculate AND score for subarray [index:end+1]
        int score = nums[index];
        for (int i = index + 1; i <= end; i++) {
            score &= nums[i];
        }
        
        partition[partitionSize] = end;
        backtrack(nums, n, end + 1, partition, partitionSize + 1, currentSum + score);
    }
}

int solution(int* nums, int n) {
    minSum = INT_MAX;
    maxSubarrays = 0;
    int* partition = (int*)malloc(n * sizeof(int));
    backtrack(nums, n, 0, partition, 0, 0);
    free(partition);
    return maxSubarrays;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n²)

2^n possible partitions, each taking O(n²) to calculate scores

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~25 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Partitions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler