Skip to main content
Talentd

Minimum Sum of Values by Dividing Array - Solution & Explanation

HardArrayBinary SearchDynamic ProgrammingBit Manipulation22 min readAsked at: Google
Practice this problem

Problem Statement

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. [1,4] as 1 & 4 == 0.
  2. [3] as the bitwise AND of a single element subarray is that element itself.
  3. [3] as the bitwise AND of a single element subarray is that element itself.
  4. [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:

  1. [[2,3,5],[7,7,7],[5]] with the sum of the values 5 + 7 + 5 == 17.
  2. [[2,3,5,7],[7,7],[5]] with the sum of the values 7 + 7 + 5 == 19.
  3. [[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 <= 104
  • 1 <= m == andValues.length <= min(n, 10)
  • 1 <= nums[i] < 105
  • 0 <= 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

This approach attempts to find the valid partitions through a direct iteration and backtracking method. By iterating over potential split points within the array and evaluating whether a valid subarray can be formed for the current required `andValue`, we explore feasible divisions and backtrack when necessary.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming with Prefix AND

This approach involves using a prefix AND array to efficiently calculate potential subarray AND values. By pre-computing the AND of all subarrays and carefully iterating through potential splits that match these prefix calculations with the required `andValues`, we can directly determine and sum valid configurations.

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

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 into m - j subarrays, return +infty.
  • If 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.
  • Otherwise, we perform a bitwise AND operation on 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:
    • 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].
  • 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n * m), due to the space needed for memoizing previously calculated results.

Dynamic Programming with Prefix AND

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.

Memoization Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with BacktrackingExponential worst caseO(m)Useful for understanding valid split exploration and pruning with AND monotonicity
Dynamic Programming with Prefix ANDO(n * m * logV)O(n * m)Best general solution for large inputs; efficiently tracks segment transitions

Video Solution

3117. Minimum Sum of Values by Dividing Array | DP | Math | Probabitly | Bit Manipulation (AND) • Aryan Mittal • 3,662 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Sum of Values by Dividing Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Subarray With Bitwise OR Closest to K

Next

Find X Value of Array II