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.
The C code employs recursive backtracking accompanied by memoization to keep track of results computed for specific indices. The objective is to iterate over every potential point to a form a subarray that satisfies the specified bitwise AND condition. This recursive logic checks potential subarray formations and backtracks as necessary.
Time Complexity: O(n * m^2), where n is the number of elements in `nums` and m is the number of partitions. This accounts for the exploration of subarrays with recursive branching.
Space Complexity: O(n * m), due to the space needed for memoizing previously calculated results.
The code maintains an AND-prefix array allowing quick determination of the AND result for any given subarray of `nums`. Dynamic programming is leveraged, iterating possible subarrays and checking against the target `andValues`. If a match is found, the dp table is updated with the sum of the last element of the current subarray.
Time Complexity: O(n^2 * m), as it requires pairwise iterating through potential subarray splits.
Space Complexity: O(n * m), with matrices holding subproblem solutions.
We design a function dfs(i, j, a), which represents the possible minimum sum of subarray values that can be obtained starting from the i-th element, with j subarrays already divided, and the bitwise AND result of the current subarray to be divided is a. The answer is dfs(0, 0, -1).
The execution process of the function dfs(i, j, a) is as follows:
n - i < m - j, it means that the remaining elements are not enough to divide into m - j subarrays, return +infty.j = m, it means that m subarrays have been divided. At this time, check whether i = n holds. If it holds, return 0, otherwise return +infty.a and nums[i] to get a new a. If a < andValues[j], it means that the bitwise AND result of the current subarray to be divided does not meet the requirements, return +infty. Otherwise, we have two choices:dfs(i + 1, j, a).dfs(i + 1, j + 1, -1) + nums[i].To avoid repeated calculations, we use the method of memoization search and store the result of dfs(i, j, a) in a hash table.
The time complexity is O(n times m times log M), and the space complexity is O(n times m times log M). Where n and m are the lengths of the arrays nums and andValues respectively; and M is the maximum value in the array nums, in this problem M leq 10^5.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach with Backtracking | Time Complexity: O(n * m^2), where n is the number of elements in `nums` and m is the number of partitions. This accounts for the exploration of subarrays with recursive branching. |
| Dynamic Programming with Prefix AND | Time Complexity: O(n^2 * m), as it requires pairwise iterating through potential subarray splits. |
| Memoization Search | — |
| 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 |
3117. Minimum Sum of Values by Dividing Array | DP | Math | Probabitly | Bit Manipulation (AND) • Aryan Mittal • 3,602 views views
Watch 6 more video solutions →Practice Minimum Sum of Values by Dividing Array with our built-in code editor and test cases.
Practice on FleetCode