#2871
Split Array Into Maximum Number of Subarrays
specialist · 990 · lc medium +32 · verified · 42.3% accepted · 245 likes · top 23%
Description
An array nums of non-negative integers is given. The score of subarray nums[l..r] is nums[l] AND nums[l + 1] AND ... AND nums[r] (bitwise AND).
Partition the array into one or more contiguous subarrays (each element in exactly one) so that the total score sum is as small as possible. Among all such partitions with minimum total score, return the maximum number of subarrays.
A subarray is a contiguous part of the array.
Example 1:
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:
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.
Code
1
2
3