Watch 7 video solutions for Minimum Sum of Values by Dividing Array, a hard level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by Aryan Mittal has 3,602 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two arrays nums and andValues of length n and m respectively.
The value of an array is equal to the last element of that array.
You have to divide nums into m disjoint contiguous subarrays such that for the ith subarray [li, ri], the bitwise AND of the subarray elements is equal to andValues[i], in other words, nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i] for all 1 <= i <= m, where & represents the bitwise AND operator.
Return the minimum possible sum of the values of the m subarrays nums is divided into. If it is not possible to divide nums into m subarrays satisfying these conditions, return -1.
Example 1:
Input: nums = [1,4,3,3,2], andValues = [0,3,3,2]
Output: 12
Explanation:
The only possible way to divide nums is:
[1,4] as 1 & 4 == 0.[3] as the bitwise AND of a single element subarray is that element itself.[3] as the bitwise AND of a single element subarray is that element itself.[2] as the bitwise AND of a single element subarray is that element itself.The sum of the values for these subarrays is 4 + 3 + 3 + 2 = 12.
Example 2:
Input: nums = [2,3,5,7,7,7,5], andValues = [0,7,5]
Output: 17
Explanation:
There are three ways to divide nums:
[[2,3,5],[7,7,7],[5]] with the sum of the values 5 + 7 + 5 == 17.[[2,3,5,7],[7,7],[5]] with the sum of the values 7 + 7 + 5 == 19.[[2,3,5,7,7],[7],[5]] with the sum of the values 7 + 7 + 5 == 19.The minimum possible sum of the values is 17.
Example 3:
Input: nums = [1,2,3,4], andValues = [2]
Output: -1
Explanation:
The bitwise AND of the entire array nums is 0. As there is no possible way to divide nums into a single subarray to have the bitwise AND of elements 2, return -1.
Constraints:
1 <= n == nums.length <= 1041 <= m == andValues.length <= min(n, 10)1 <= nums[i] < 1050 <= andValues[j] < 105Problem Overview: You are given an array nums and another array andValues. The task is to divide nums into exactly m contiguous segments so that the bitwise AND of each segment equals the corresponding value in andValues. Among all valid ways to divide the array, return the minimum possible sum of the last element of every segment.
Approach 1: Greedy with Backtracking (Exponential worst case, optimized with pruning)
This method scans the array while maintaining the running bitwise AND for the current segment. Once the running AND matches the target value from andValues, you can close the segment and start a new one. However, multiple valid cut positions may exist, so backtracking explores different split points while pruning impossible states where the AND already becomes smaller than the target. The key observation is that bitwise AND only decreases as the segment grows, which helps terminate branches early. Time complexity is worst‑case O(n * 2^m) depending on splits, with O(m) recursion space. This approach demonstrates the constraints clearly but can struggle with large inputs.
Approach 2: Dynamic Programming with Prefix AND (O(n * m * logV) time, O(n * m) space)
The optimized approach uses dynamic programming combined with incremental bitwise AND tracking. Define dp[i][j] as the minimum cost after processing the first i elements and forming j valid segments. While extending a segment ending at index i, compute the running AND of the subarray and stop once it drops below the required andValues[j]. When the AND matches exactly, update the DP state using the segment's last element cost. Efficient implementations maintain candidate segment starts using queues or precomputed AND transitions, similar to techniques used in bit manipulation problems and range queries handled by a segment tree. Time complexity is roughly O(n * m * logV) due to distinct AND states per position, with O(n * m) space.
Recommended for interviews: The dynamic programming approach with prefix AND is the expected solution. It shows you understand how bitwise AND behaves across ranges and how to combine it with DP state transitions. Mentioning the greedy/backtracking idea first demonstrates problem exploration, while the DP optimization proves you can reduce exponential branching into structured state transitions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Backtracking | Exponential worst case | O(m) | Useful for understanding valid split exploration and pruning with AND monotonicity |
| Dynamic Programming with Prefix AND | O(n * m * logV) | O(n * m) | Best general solution for large inputs; efficiently tracks segment transitions |