Minimum Sum of Values by Dividing Array
HardPrompt
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]as1 & 4 == 0.[3]as the bitwiseANDof a single element subarray is that element itself.[3]as the bitwiseANDof a single element subarray is that element itself.[2]as the bitwiseANDof 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 values5 + 7 + 5 == 17.[[2,3,5,7],[7,7],[5]]with the sum of the values7 + 7 + 5 == 19.[[2,3,5,7,7],[7],[5]]with the sum of the values7 + 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] < 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores all possible ways to partition the nums array into m subarrays. A recursive function solve(i, j) is defined, which tries to find a valid partition for the suffix of nums starting at index i and the suffix of andValues starting at index j.
Algorithm
- Define a recursive function
solve(startIndex, andIndex). - Base Case 1: If
andIndex == m(allandValuesare matched), return 0 ifstartIndex == n(allnumsare used), otherwise return a large value (infinity) to signify an invalid partition. - Base Case 2: If
startIndex == nbutandIndex < m, return infinity as it's impossible to form more subarrays. - Initialize
minSum = infinityandcurrentAnd = -1(all bits 1). - Loop
kfromstartIndexton-1:- Update
currentAndby ANDing withnums[k]. - If
currentAnd == andValues[andIndex]:- Recursively call
res = solve(k + 1, andIndex + 1). - If
resis not infinity, updateminSum = min(minSum, nums[k] + res).
- Recursively call
- Update
- Return
minSum. - The initial call is
solve(0, 0). If it returns infinity, no solution exists, so return -1.
Walkthrough
The function solve(i, j) aims to find the minimum sum for partitioning nums[i:] to match andValues[j:].
It iterates through all possible end points k for the j-th subarray, which starts at i.
For each k, it calculates the bitwise AND of nums[i...k].
If this AND value equals andValues[j], it makes a recursive call solve(k+1, j+1) to solve the rest of the problem.
The total sum for this partition is nums[k] (the value of the current subarray) plus the result of the recursive call.
The function returns the minimum sum found among all valid k.
Base cases handle scenarios where we have successfully partitioned the whole array or run out of elements.
class Solution { private static final int INF = Integer.MAX_VALUE / 2; private int[] nums; private int[] andValues; private int n, m; public int minimumValueSum(int[] nums, int[] andValues) { this.nums = nums; this.andValues = andValues; this.n = nums.length; this.m = andValues.length; int result = solve(0, 0); return result >= INF ? -1 : result; } private int solve(int i, int j) { // Base case: successfully formed m subarrays if (j == m) { return (i == n) ? 0 : INF; } // Base case: ran out of numbers in nums but still need to form subarrays if (i == n) { return INF; } int minSum = INF; int currentAnd = -1; // Represents all bits set to 1 // Iterate through all possible end points 'k' for the j-th subarray for (int k = i; k < n; k++) { if (currentAnd == -1) { currentAnd = nums[k]; } else { currentAnd &= nums[k]; } if (currentAnd == andValues[j]) { int restSum = solve(k + 1, j + 1); if (restSum < INF) { minSum = Math.min(minSum, nums[k] + restSum); } } } return minSum; }}Complexity
Time
Exponential, roughly `O(C(n-1, m-1) * n)`, where `C` is the binomial coefficient. This is because it explores every possible partition of the `nums` array into `m` subarrays.
Space
`O(m)` due to the recursion stack depth, as the recursion goes as deep as the number of subarrays `m`.
Trade-offs
Pros
Simple to conceptualize and implement.
Cons
Extremely inefficient and will result in a Time Limit Exceeded (TLE) error for most of the constraints.
This approach improves upon the brute-force recursion by using memoization to store the results of subproblems, avoiding redundant calculations. The state of our DP is defined by (i, j), representing the subproblem for nums[i:] and andValues[j:].
Algorithm
- Create a memoization table
memo[n+1][m+1]initialized with a value indicating "not computed" (e.g., -1). - Define a recursive function
solve(startIndex, andIndex). - Base Cases: Same as brute-force.
- Check memoization: If
memo[startIndex][andIndex]is already computed, return it. - Initialize
minSum = infinityandcurrentAnd = -1. - Loop
kfromstartIndexton-1:- Update
currentAnd &= nums[k]. - Optimization: If
(currentAnd & andValues[andIndex]) != andValues[andIndex], break the loop as further ANDing will not satisfy the condition. - If
currentAnd == andValues[andIndex]:- Recursively call
res = solve(k + 1, andIndex + 1). - If
resis not infinity, updateminSum = min(minSum, nums[k] + res).
- Recursively call
- Update
- Store the result:
memo[startIndex][andIndex] = minSum. - Return
minSum.
Walkthrough
We use a 2D array memo[i][j] to store the result of solve(i, j). Before computing solve(i, j), we check if memo[i][j] already has a computed value. If so, we return it directly.
The recursive structure is the same as the brute-force approach. The function iterates through possible endpoints k for the current subarray, and if a valid subarray is found, it makes a recursive call for the rest of the arrays.
An optimization is added: since the bitwise AND is a non-increasing operation, if the currentAnd value becomes "incompatible" with andValues[j], we can stop extending the current subarray. A value x is incompatible with y if (x & y) != y, meaning x has a zero bit where y has a one bit. Once this happens, ANDing with more numbers won't fix it.
import java.util.Arrays; class Solution { private static final int INF = Integer.MAX_VALUE / 2; private int[] nums; private int[] andValues; private int n, m; private int[][] memo; public int minimumValueSum(int[] nums, int[] andValues) { this.nums = nums; this.andValues = andValues; this.n = nums.length; this.m = andValues.length; this.memo = new int[n][m]; for (int[] row : memo) { Arrays.fill(row, -1); } int result = solve(0, 0); return result >= INF ? -1 : result; } private int solve(int i, int j) { if (j == m) { return (i == n) ? 0 : INF; } if (i == n) { return INF; } if (memo[i][j] != -1) { return memo[i][j]; } int minSum = INF; int currentAnd = -1; for (int k = i; k < n; k++) { if (currentAnd == -1) { currentAnd = nums[k]; } else { currentAnd &= nums[k]; } // Optimization: if currentAnd can't possibly become andValues[j] if ((currentAnd & andValues[j]) != andValues[j]) { break; } if (currentAnd == andValues[j]) { int restSum = solve(k + 1, j + 1); if (restSum < INF) { minSum = Math.min(minSum, nums[k] + restSum); } } } return memo[i][j] = minSum; }}Complexity
Time
`O(n^2 * m)`. There are `O(n*m)` states to compute. Each state computation involves a loop that can run up to `n` times in the worst case.
Space
`O(n * m)` for the memoization table. The recursion stack depth also contributes, but it's dominated by the table size.
Trade-offs
Pros
Much faster than brute-force by avoiding recomputation of overlapping subproblems.
A standard and systematic way to solve problems with optimal substructure.
Cons
The time complexity is still too high for the given constraints (
n <= 10^4), leading to a Time Limit Exceeded (TLE) verdict.
This is the most efficient approach, which optimizes the transition of the DP state. Instead of iterating through all possible endpoints k one by one, it leverages a key property of the bitwise AND operation: for a fixed starting index i, the value of nums[i] & ... & nums[k] changes a limited number of times as k increases. We can "jump" between these change points.
Algorithm
- Precompute
next_zero[i][b]for alliand bitsb. - Initialize a DP table
dp[n+1][m+1]with a large value (infinity). Setdp[n][m] = 0. - Loop
jfromm-1down to0:- Create an array
costswherecosts[k] = (k < n ? nums[k] : infinity) + (k+1 <= n ? dp[k+1][j+1] : infinity). - Build an RMQ data structure (e.g., Segment Tree) on the
costsarray. - Loop
ifromn-1down to0:- Initialize
p_curr = i,and_val = -1,min_res = infinity. - Loop while
p_curr < n:and_val &= nums[p_curr].- If
(and_val & andValues[j]) != andValues[j], break. - Find
p_next, the end of the segment where the AND-prefix fromiremainsand_val. This is done usingnext_zeroinO(L)time. - If
and_val == andValues[j]:- Query the RMQ structure on the
costsarray for the range[p_curr, p_next - 1]to getmin_cost_in_segment. - Update
min_res = min(min_res, min_cost_in_segment).
- Query the RMQ structure on the
- Set
p_curr = p_next.
- Set
dp[i][j] = min_res.
- Initialize
- Create an array
- The final answer is
dp[0][0]. If it's infinity, return -1.
Walkthrough
The DP state dp[i][j] remains the same: the minimum sum for nums[i:] and andValues[j:]. We compute it iteratively from j = m-1 down to 0.
Key Idea: For a fixed i, the sequence of AND-prefix values A(i, k) = nums[i] & ... & nums[k] has at most O(log(max(nums))) distinct values. We can iterate through segments of k where A(i, k) is constant.
Precomputation: We precompute an array next_zero[i][b], which stores the index of the first element at or after i that has a 0 in the b-th bit. This helps us quickly find the next index where the AND-prefix value will change. This takes O(n * L) time, where L is the number of bits (e.g., 17 for values up to 10^5).
DP Transition: To compute dp[i][j], we iterate through the segments of constant AND-prefix values starting from i.
- Let the current segment be
[p_curr, p_next - 1], where the AND-prefix value isv. - If
v == andValues[j], we have found a range of valid endpoints for the current subarray. We need to find the minimum ofnums[k] + dp[k+1][j+1]forkin this range.
Range Minimum Query (RMQ): This subproblem is a classic RMQ. For each j, before computing the dp values, we build a data structure (like a Segment Tree) on the array costs[k] = nums[k] + dp[k+1][j+1]. This allows us to query the minimum in a range in O(log n).
The overall process involves iterating j from m-1 to 0. For each j, we build the RMQ structure and then compute dp[i][j] for all i using the segment jumping technique.
import java.util.Arrays; class Solution { private static final int INF = Integer.MAX_VALUE / 2; private static final int BITS = 17; public int minimumValueSum(int[] nums, int[] andValues) { int n = nums.length; int m = andValues.length; int[][] next_zero = new int[n + 1][BITS]; for (int b = 0; b < BITS; b++) { next_zero[n][b] = n; } for (int i = n - 1; i >= 0; i--) { for (int b = 0; b < BITS; b++) { if (((nums[i] >> b) & 1) == 0) { next_zero[i][b] = i; } else { next_zero[i][b] = next_zero[i + 1][b]; } } } int[][] dp = new int[n + 1][m + 1]; for (int[] row : dp) { Arrays.fill(row, INF); } dp[n][m] = 0; for (int j = m - 1; j >= 0; j--) { int[] costs = new int[n]; for (int k = 0; k < n; k++) { costs[k] = (dp[k + 1][j + 1] < INF) ? nums[k] + dp[k + 1][j + 1] : INF; } SegmentTree st = new SegmentTree(costs); for (int i = n - 1; i >= 0; i--) { int p_curr = i; int and_val = -1; while (p_curr < n) { and_val &= nums[p_curr]; if ((and_val & andValues[j]) != andValues[j]) { break; } int p_next = n; for (int b = 0; b < BITS; b++) { if (((and_val >> b) & 1) == 1) { p_next = Math.min(p_next, next_zero[p_curr + 1][b]); } } if (and_val == andValues[j]) { int min_cost = st.query(p_curr, p_next - 1); if (min_cost < INF) { dp[i][j] = Math.min(dp[i][j], min_cost); } } p_curr = p_next; } } } return dp[0][0] >= INF ? -1 : dp[0][0]; }} class SegmentTree { private int[] tree; private int n; public SegmentTree(int[] arr) { n = arr.length; tree = new int[4 * n]; build(arr, 0, 0, n - 1); } private void build(int[] arr, int node, int start, int end) { if (start == end) { tree[node] = arr[start]; } else { int mid = start + (end - start) / 2; build(arr, 2 * node + 1, start, mid); build(arr, 2 * node + 2, mid + 1, end); tree[node] = Math.min(tree[2 * node + 1], tree[2 * node + 2]); } } public int query(int l, int r) { if (l > r) return Integer.MAX_VALUE / 2; return query(0, 0, n - 1, l, r); } private int query(int node, int start, int end, int l, int r) { if (r < start || end < l) { return Integer.MAX_VALUE / 2; } if (l <= start && end <= r) { return tree[node]; } int mid = start + (end - start) / 2; int p1 = query(2 * node + 1, start, mid, l, r); int p2 = query(2 * node + 2, mid + 1, end, l, r); return Math.min(p1, p2); }}Complexity
Time
`O(m * (n * log(n) + n * L^2))`, where `L` is `log(max(nums))`. For each of the `m` stages, we build a segment tree in `O(n log n)` and then compute `n` DP states. Each DP state takes `O(L^2)` because the inner while loop runs `O(L)` times, and finding `p_next` takes `O(L)`.
Space
`O(n * (m + L))`. This is for the `dp` table (`n*m`), the `next_zero` table (`n*L`), and the segment tree (`4*n`).
Trade-offs
Pros
Highly efficient and passes the given constraints.
A clever optimization based on the properties of bitwise operations and standard data structures.
Cons
Significantly more complex to understand and implement correctly compared to simpler DP approaches.
Solutions
Solution
class Solution {private int[] nums;private int[] andValues;private final int inf = 1 << 29;private Map<Long, Integer> f = new HashMap<>();public int minimumValueSum(int[] nums, int[] andValues) { this.nums = nums; this.andValues = andValues; int ans = dfs(0, 0, -1); return ans >= inf ? -1 : ans; }private int dfs(int i, int j, int a) { if (nums.length - i < andValues.length - j) { return inf; } if (j == andValues.length) { return i == nums.length ? 0 : inf; } a &= nums[i]; if (a < andValues[j]) { return inf; } long key = (long)i << 36 | (long)j << 32 | a; if (f.containsKey(key)) { return f.get(key); } int ans = dfs(i + 1, j, a); if (a == andValues[j]) { ans = Math.min(ans, dfs(i + 1, j + 1, -1) + nums[i]); } f.put(key, ans); return ans; }}class Solution {public: int minimumValueSum(vector<int> &nums, vector<int> &andValues) { this->nums = nums; this->andValues = andValues; n = nums.size(); m = andValues.size(); int ans = dfs(0, 0, -1); return ans >= inf ? -1 : ans; } private: vector<int> nums; vector<int> andValues; int n; int m; const int inf = 1 << 29; unordered_map<long long, int> f; int dfs(int i, int j, int a) { if (n - i < m - j) { return inf; } if (j == m) { return i == n ? 0 : inf; } a &= nums[i]; if (a < andValues[j]) { return inf; } long long key = (long long)i << 36 | (long long)j << 32 | a; if (f.contains(key)) { return f[key]; } int ans = dfs(i + 1, j, a); if (a == andValues[j]) { ans = min(ans, dfs(i + 1, j + 1, -1) + nums[i]); } return f[key] = ans; }};class Solution: def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int: @ cache def dfs(i: int, j: int, a: int) -> int: if n - i < m - j: return inf if j == m: return 0 if i == n else inf a &= nums[i] if a < andValues[j]: return inf ans = dfs(i + 1, j, a) if a == andValues[j]: ans = min(ans, dfs(i + 1, j + 1, - 1) + nums[i]) return ans n, m = len(nums), len(andValues) ans = dfs(0, 0, - 1) return ans if ans < inf else - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.