Scale Engineer

Minimum Sum of Values by Dividing Array

Hard
#2770Time: 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`.
Patterns
Dynamic ProgrammingBit Manipulation
Algorithms
Binary Search
Data structures
ArraySegment TreeQueue

Prompt

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

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 (all andValues are matched), return 0 if startIndex == n (all nums are used), otherwise return a large value (infinity) to signify an invalid partition.
  • Base Case 2: If startIndex == n but andIndex < m, return infinity as it's impossible to form more subarrays.
  • Initialize minSum = infinity and currentAnd = -1 (all bits 1).
  • Loop k from startIndex to n-1:
    • Update currentAnd by ANDing with nums[k].
    • If currentAnd == andValues[andIndex]:
      • Recursively call res = solve(k + 1, andIndex + 1).
      • If res is not infinity, update minSum = min(minSum, nums[k] + res).
  • 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.

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem