Minimum Sum of Values by Dividing Array solution and explanation
Google
6 more videos on this problem
3117. Minimum Sum of Values by Dividing Array | DP | Math | Probabitly | Bit Manipulation (AND)Aryan Mittal · 22:35 · 3K views
Minimum Sum of Values by Dividing Array | Recursion | Memoization | Leetcode 3117 | codestorywithMIKcodestorywithMIK · 1:00:00 · 3K views
3117. Minimum Sum of Values by Dividing Array | Weekly Leetcode 393codingMohan · 1:00:10 · 1K views
3117. Minimum Sum of Values by Dividing Array (Leetcode Hard)Programming Live with Larry · 3:37:02 · 521 views
3117. Minimum Sum of Values by Dividing Array | Weekly Contest 393 - 4th Problem | 0-1 DPTech Courses · 14:43 · 99 views
DECODE DSA #LEVEL UP #CONTEST SOL.#leetcode#challenge#Minimum Sum of Val. by Dividing Array#LC-3117Decode · 5:56 · 14 views
Leetcode 3117. Minimum Sum of Values by Dividing Array(dfs + memo)LetsCode · 7:18 · 11 views
The problem
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
Approach overview
Problem 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 1: Greedy Approach with Backtracking
def minimum_sum(nums, and_values):
def dfs(index, a_index, memo):
if a_index == len(and_values):
return 0 if index == len(nums) else float('inf')
if memo[index][a_index] != -1:
return memo[index][a_index]
min_sum = float('inf')
and_res = nums[index]
for j in range(index, len(nums)):
and_res &= nums[j]
if and_res == and_values[a_index]:
res = dfs(j + 1, a_index + 1, memo)
if res != float('inf'):
min_sum = min(min_sum, res + nums[j])
memo[index][a_index] = min_sum
return min_sum
memo = [[-1] * len(and_values) for _ in range(len(nums))]
result = dfs(0, 0, memo)
return -1 if result == float('inf') else result
nums = [2, 3, 5, 7, 7, 5]
and_values = [0, 7, 5]
print(minimum_sum(nums, and_values))import java.util.*;
public class MinimumSum {
private int dfs(int[] nums, int[] andValues, int index, int aIndex, int[][] memo) {
if (aIndex == andValues.length) return index == nums.length ? 0 : Integer.MAX_VALUE;
if (memo[index][aIndex] != -1) return memo[index][aIndex];
int minSum = Integer.MAX_VALUE;
int andRes = nums[index];
for (int j = index; j < nums.length; ++j) {
andRes &= nums[j];
if (andRes == andValues[aIndex]) {
int res = dfs(nums, andValues, j + 1, aIndex + 1, memo);
if (res != Integer.MAX_VALUE) {
minSum = Math.min(minSum, res + nums[j]);
}
}
}
return memo[index][aIndex] = minSum;
}
public int minimumSum(int[] nums, int[] andValues) {
int[][] memo = new int[nums.length][andValues.length];
for (int[] row : memo) Arrays.fill(row, -1);
int result = dfs(nums, andValues, 0, 0, memo);
return result == Integer.MAX_VALUE ? -1 : result;
}
public static void main(String[] args) {
MinimumSum ms = new MinimumSum();
int[] nums = {2,3,5,7,7,5};
int[] andValues = {0,7,5};
System.out.println(ms.minimumSum(nums, andValues));
}
}#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int dfs(vector<int>& nums, vector<int>& andValues, int index, int aIndex, vector<vector<int>>& memo) {
if (aIndex == andValues.size()) return index == nums.size() ? 0 : INT_MAX;
if (memo[index][aIndex] != -1) return memo[index][aIndex];
int minValue = INT_MAX;
int andRes = nums[index];
for (int j = index; j < nums.size(); ++j) {
andRes &= nums[j];
if (andRes == andValues[aIndex]) {
int res = dfs(nums, andValues, j + 1, aIndex + 1, memo);
if (res != INT_MAX) {
minValue = min(minValue, res + nums[j]);
}
}
}
return memo[index][aIndex] = minValue;
}
int minimumSum(vector<int>& nums, vector<int>& andValues) {
vector<vector<int>> memo(nums.size(), vector<int>(andValues.size(), -1));
int result = dfs(nums, andValues, 0, 0, memo);
return result == INT_MAX ? -1 : result;
}
int main() {
vector<int> nums = {2,3,4,8,10};
vector<int> andValues = {0,2};
cout << minimumSum(nums, andValues) << endl;
return 0;
}function minimumSum(nums, andValues) {
const n = nums.length;
const m = andValues.length;
const memo = Array.from({ length: n }, () => Array(m).fill(-1));
function dfs(index, aIndex) {
if (aIndex === m) return index === n ? 0 : Number.MAX_SAFE_INTEGER;
if (memo[index][aIndex] !== -1) return memo[index][aIndex];
let minSum = Number.MAX_SAFE_INTEGER;
let andRes = nums[index];
for (let j = index; j < n; ++j) {
andRes &= nums[j];
if (andRes === andValues[aIndex]) {
const res = dfs(j + 1, aIndex + 1);
if (res !== Number.MAX_SAFE_INTEGER) {
minSum = Math.min(minSum, res + nums[j]);
}
}
}
return memo[index][aIndex] = minSum;
}
const result = dfs(0, 0);
return result === Number.MAX_SAFE_INTEGER ? -1 : result;
}
const nums = [2, 3, 5, 7, 7, 5];
const andValues = [0, 7, 5];
console.log(minimumSum(nums, andValues));#include <stdio.h>
#include <limits.h>
int solve(int* nums, int n, int* andValues, int m, int index, int aIndex, int** memo) {
if (aIndex == m) return index == n ? 0 : INT_MAX;
if (memo[index][aIndex] != -1) return memo[index][aIndex];
int result = INT_MAX;
int andVal = nums[index];
for (int j = index; j < n; ++j) {
andVal &= nums[j];
if (andVal == andValues[aIndex]) {
int res = solve(nums, n, andValues, m, j + 1, aIndex + 1, memo);
if (res != INT_MAX) {
result = (result < andVal + nums[j]) ? result : andVal + nums[j];
}
}
}
memo[index][aIndex] = result;
return result;
}
int minimumSum(int* nums, int numsSize, int* andValues, int andValuesSize) {
int** memo = (int**)malloc(numsSize * sizeof(int*));
for (int i = 0; i < numsSize; ++i) {
memo[i] = (int*)malloc(andValuesSize * sizeof(int));
for (int j = 0; j < andValuesSize; ++j) {
memo[i][j] = -1;
}
}
int result = solve(nums, numsSize, andValues, andValuesSize, 0, 0, memo);
for (int i = 0; i < numsSize; ++i) free(memo[i]);
free(memo);
return result == INT_MAX ? -1 : result;
}
int main() {
int nums[] = {2,3,5,7,7,7,5};
int andValues[] = {0,7,5};
printf("%d\n", minimumSum(nums, 7, andValues, 3));
return 0;
}using System;
public class MinimumSum {
private static int Dfs(int[] nums, int[] andValues, int index, int aIndex, int[][] memo) {
if (aIndex == andValues.Length) return index == nums.Length ? 0 : Int32.MaxValue;
if (memo[index][aIndex] != -1) return memo[index][aIndex];
int minSum = Int32.MaxValue;
int andRes = nums[index];
for (int j = index; j < nums.Length; ++j) {
andRes &= nums[j];
if (andRes == andValues[aIndex]) {
int res = Dfs(nums, andValues, j + 1, aIndex + 1, memo);
if (res != Int32.MaxValue) {
minSum = Math.Min(minSum, res + nums[j]);
}
}
}
memo[index][aIndex] = minSum;
return minSum;
}
public static int MinimumSum(int[] nums, int[] andValues) {
int[][] memo = new int[nums.Length][];
for (int i = 0; i < nums.Length; ++i) {
memo[i] = new int[andValues.Length];
Array.Fill(memo[i], -1);
}
int result = Dfs(nums, andValues, 0, 0, memo);
return result == Int32.MaxValue ? -1 : result;
}
public static void Main(string[] args) {
int[] nums = {2,3,5,7,7,5};
int[] andValues = {0,7,5};
Console.WriteLine(MinimumSum(nums, andValues));
}
}The Python implementation follows a similar recursive backtracking algorithm with memoization for efficiency. Here, each sub-recursion explores potential subcharges for a valid `andValue` and saves results to avoid recalculation. Python's dynamic list structures facilitate clean memo management and recursion.
Time Complexity: O(n * m^2), with n and m being the lengths of `nums` and `andValues`, resulting from depth-wise exploration and constraints.
Space Complexity: O(n * m) space for recording subproblem solutions in memoization.
Approach 2: Dynamic Programming with Prefix AND
def prefix_minimum_sum(nums, and_values):
n = len(nums)
m = len(and_values)
AND_prefix = [0] * (n + 1)
AND_prefix[0] = ~0 # All 1s in binary
for i in range(1, n + 1):
AND_prefix[i] = AND_prefix[i - 1] & nums[i - 1]
dp = [[float('inf')] * (m + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
for k in range(i):
and_segment = AND_prefix[i] & ~AND_prefix[k]
if and_segment == and_values[j - 1]:
dp[i][j] = min(dp[i][j], dp[k][j - 1] + nums[i - 1])
result = dp[n][m]
return -1 if result == float('inf') else result
nums = [2,3,5,7,7,5]
and_values = [0,7,5]
print(prefix_minimum_sum(nums, and_values))#include <vector>
#include <iostream>
#include <climits>
using namespace std;
int prefixMinimumSum(vector<int>& nums, vector<int>& andValues) {
int n = nums.size();
int m = andValues.size();
vector<int> AND_prefix(n + 1, ~0);
for (int i = 1; i <= n; ++i) {
AND_prefix[i] = AND_prefix[i - 1] & nums[i - 1];
}
vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = 0; k < i; ++k) {
int and_segment = AND_prefix[i] & ~AND_prefix[k];
if (and_segment == andValues[j - 1]) {
dp[i][j] = min(dp[i][j], dp[k][j - 1] + nums[i - 1]);
}
}
}
}
int result = dp[n][m];
return result == INT_MAX ? -1 : result;
}
int main() {
vector<int> nums = {2, 3, 5, 7, 7, 5};
vector<int> andValues = {0, 7, 5};
cout << prefixMinimumSum(nums, andValues) << endl;
return 0;
}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.
Approach 3: Memoization Search
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:
- If
n - i < m - j, it means that the remaining elements are not enough to divide intom - jsubarrays, return+infty. - If
j = m, it means thatmsubarrays have been divided. At this time, check whetheri = nholds. If it holds, return0, otherwise return+infty. - Otherwise, we perform a bitwise AND operation on
aandnums[i]to get a newa. Ifa < 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:- Do not divide the current element, i.e.,
dfs(i + 1, j, a). - Divide the current element, i.e.,
dfs(i + 1, j + 1, -1) + nums[i].
- Do not divide the current element, i.e.,
- Return the minimum of the above two choices.
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.
function minimumValueSum(nums: number[], andValues: number[]): number {
const [n, m] = [nums.length, andValues.length];
const f: Map<bigint, number> = new Map();
const dfs = (i: number, j: number, a: number): number => {
if (n - i < m - j) {
return Infinity;
}
if (j === m) {
return i === n ? 0 : Infinity;
}
a &= nums[i];
if (a < andValues[j]) {
return Infinity;
}
const key = (BigInt(i) << 36n) | (BigInt(j) << 32n) | BigInt(a);
if (f.has(key)) {
return f.get(key)!;
}
let ans = dfs(i + 1, j, a);
if (a === andValues[j]) {
ans = Math.min(ans, dfs(i + 1, j + 1, -1) + nums[i]);
}
f.set(key, ans);
return ans;
};
const ans = dfs(0, 0, -1);
return ans >= Infinity ? -1 : ans;
}func minimumValueSum(nums []int, andValues []int) int {
n, m := len(nums), len(andValues)
f := map[int]int{}
const inf int = 1 << 29
var dfs func(i, j, a int) int
dfs = func(i, j, a int) int {
if n-i < m-j {
return inf
}
if j == m {
if i == n {
return 0
}
return inf
}
a &= nums[i]
if a < andValues[j] {
return inf
}
key := i<<36 | j<<32 | a
if v, ok := f[key]; ok {
return v
}
ans := dfs(i+1, j, a)
if a == andValues[j] {
ans = min(ans, dfs(i+1, j+1, -1)+nums[i])
}
f[key] = ans
return ans
}
if ans := dfs(0, 0, -1); ans < inf {
return ans
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Backtracking | Time Complexity: O(n * m^2), with n and m being the lengths of `nums` and `andValues`, resulting from depth-wise exploration and constraints. |
| Dynamic Programming with Prefix AND | Time Complexity: O(n^2 * m), as it requires pairwise iterating through potential subarray splits. |
| Memoization Search | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Sum of Values by Dividing Array easy or hard?
Minimum Sum of Values by Dividing Array is classified as a Hard problem on LeetCode with an acceptance rate around 28%. The difficulty comes from combining segment partitioning with bitwise AND properties and optimizing the search using dynamic programming.
Minimum Sum of Values by Dividing Array Python/Java solution
Both Python and Java implementations typically use dynamic programming where dp[i][j] stores the minimum cost after forming j segments using the first i elements. While extending segments, maintain the running bitwise AND and update the DP state when it matches the required target value.
How to solve Minimum Sum of Values by Dividing Array in O(n)?
A strict O(n) solution is generally not achievable because the algorithm must evaluate multiple possible segment boundaries and AND states. Efficient implementations reduce the search using prefix AND compression and DP transitions, bringing the complexity close to O(n * m * logV).
What is the best approach for Minimum Sum of Values by Dividing Array?
Dynamic programming with prefix AND is the most reliable approach. It tracks the minimum cost for forming segments while computing running bitwise AND values for subarrays. Because bitwise AND values decrease monotonically, the number of distinct states per index is small, allowing an efficient O(n * m * logV) solution.
Is Minimum Sum of Values by Dividing Array asked at Google/Amazon/Meta?
Hard array and dynamic programming problems involving bitwise operations are common in interviews at companies like Google, Amazon, and Meta. This problem combines segmentation, DP state transitions, and bit manipulation, which are typical patterns in advanced coding rounds.
What data structure is used in Minimum Sum of Values by Dividing Array?
The core techniques involve dynamic programming and bit manipulation with running prefix AND values. Some optimized implementations also use queues or segment-tree-like range tracking to manage candidate segment starts efficiently.
What is the time complexity of Minimum Sum of Values by Dividing Array?
The optimized dynamic programming solution runs in about O(n * m * logV), where n is the array length, m is the number of required segments, and V represents the maximum integer value affecting distinct AND states. Space complexity is O(n * m) for storing DP states.