Split array into maximum number of subarrays

Array Greedy Bit Manipulation

42.3% acceptance

Feb 25, 2026

245

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_subarrays(nums: Vec<i32>) -> i32 {
    // Minimum score = AND of all elements
    let total_and = nums.iter().fold(!0i32, |acc, &v| acc & v);
    if total_and != 0 {
      return 1; // Can only keep as one piece
    }
    // Split greedily: whenever current AND becomes 0, cut here
    let mut cur_and = !0i32;
    let mut count = 0;
    for &v in &nums {
      cur_and &= v;
      if cur_and == 0 {
        count += 1;
        cur_and = !0i32;
      }
    }
    count.max(1)
  }
}