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 _theminimum possible sum of the values of the _m subarraysnums is divided into. If it is not possible to dividenums intom subarrays satisfying these conditions, return -1.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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 <= 10^4
  • 1 <= m == andValues.length <= min(n, 10)
  • 1 <= nums[i] < 10^5
  • 0 <= andValues[j] < 10^5

Solution

Method 1 – DP with Bitmask and Sliding Window

Intuition

Since m (number of subarrays) is small, we can use DP to try all possible partitions. For each partition, we check if the subarray’s AND matches the required value and keep track of the minimum sum of last elements.

Approach

  1. Use dp[i][j]: minimum sum for first i elements and j subarrays.
  2. For each position i and subarray k, try all possible previous positions p (where previous subarray ends).
  3. For each [p, i], compute AND and check if it matches andValues[k].
  4. If valid, update dp[i][k] with dp[p][k-1] + nums[i-1].
  5. Return dp[n][m] if possible, else -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minimumSum(vector<int>& nums, vector<int>& andValues) {
        int n = nums.size(), m = andValues.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1, INT_MAX));
        dp[0][0] = 0;
        for (int k = 1; k <= m; ++k) {
            for (int i = k; i <= n; ++i) {
                int val = nums[i-1];
                for (int j = i-1; j >= k-1; --j) {
                    val &= nums[j];
                    if (val == andValues[k-1] && dp[j][k-1] != INT_MAX)
                        dp[i][k] = min(dp[i][k], dp[j][k-1] + nums[i-1]);
                }
            }
        }
        return dp[n][m] == INT_MAX ? -1 : dp[n][m];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func minimumSum(nums []int, andValues []int) int {
    n, m := len(nums), len(andValues)
    dp := make([][]int, n+1)
    for i := range dp { dp[i] = make([]int, m+1); for j := range dp[i] { dp[i][j]=1<<30 } }
    dp[0][0]=0
    for k := 1; k <= m; k++ {
        for i := k; i <= n; i++ {
            val := nums[i-1]
            for j := i-1; j >= k-1; j-- {
                val &= nums[j]
                if val == andValues[k-1] && dp[j][k-1] < 1<<30 {
                    if dp[i][k] > dp[j][k-1]+nums[i-1] {
                        dp[i][k] = dp[j][k-1]+nums[i-1]
                    }
                }
            }
        }
    }
    if dp[n][m] == 1<<30 { return -1 }
    return dp[n][m]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int minimumSum(int[] nums, int[] andValues) {
        int n = nums.length, m = andValues.length;
        int[][] dp = new int[n+1][m+1];
        for (int[] d : dp) Arrays.fill(d, Integer.MAX_VALUE);
        dp[0][0]=0;
        for (int k=1;k<=m;k++) {
            for (int i=k;i<=n;i++) {
                int val=nums[i-1];
                for (int j=i-1;j>=k-1;j--) {
                    val&=nums[j];
                    if (val==andValues[k-1] && dp[j][k-1]!=Integer.MAX_VALUE)
                        dp[i][k]=Math.min(dp[i][k],dp[j][k-1]+nums[i-1]);
                }
            }
        }
        return dp[n][m]==Integer.MAX_VALUE?-1:dp[n][m];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun minimumSum(nums: IntArray, andValues: IntArray): Int {
        val n = nums.size; val m = andValues.size
        val dp = Array(n+1) { IntArray(m+1) { Int.MAX_VALUE } }
        dp[0][0]=0
        for (k in 1..m) {
            for (i in k..n) {
                var val_ = nums[i-1]
                for (j in i-1 downTo k-1) {
                    val_ = val_ and nums[j]
                    if (val_==andValues[k-1] && dp[j][k-1]!=Int.MAX_VALUE)
                        dp[i][k]=minOf(dp[i][k],dp[j][k-1]+nums[i-1])
                }
            }
        }
        return if (dp[n][m]==Int.MAX_VALUE) -1 else dp[n][m]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def minimumSum(self, nums: list[int], andValues: list[int]) -> int:
        n, m = len(nums), len(andValues)
        dp = [[float('inf')] * (m+1) for _ in range(n+1)]
        dp[0][0] = 0
        for k in range(1, m+1):
            for i in range(k, n+1):
                val = nums[i-1]
                for j in range(i-1, k-2, -1):
                    val &= nums[j]
                    if val == andValues[k-1] and dp[j][k-1] < float('inf'):
                        dp[i][k] = min(dp[i][k], dp[j][k-1] + nums[i-1])
        return -1 if dp[n][m] == float('inf') else dp[n][m]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn minimum_sum(nums: Vec<i32>, and_values: Vec<i32>) -> i32 {
        let n = nums.len(); let m = and_values.len();
        let mut dp = vec![vec![i32::MAX; m+1]; n+1];
        dp[0][0]=0;
        for k in 1..=m {
            for i in k..=n {
                let mut val = nums[i-1];
                for j in (k-1..=i-1).rev() {
                    val &= nums[j];
                    if val==and_values[k-1] && dp[j][k-1]!=i32::MAX {
                        dp[i][k]=dp[i][k].min(dp[j][k-1]+nums[i-1]);
                    }
                }
            }
        }
        if dp[n][m]==i32::MAX { -1 } else { dp[n][m] }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    minimumSum(nums: number[], andValues: number[]): number {
        const n = nums.length, m = andValues.length;
        const dp = Array.from({length:n+1},()=>Array(m+1).fill(Infinity));
        dp[0][0]=0;
        for (let k=1;k<=m;k++) {
            for (let i=k;i<=n;i++) {
                let val=nums[i-1];
                for (let j=i-1;j>=k-1;j--) {
                    val&=nums[j];
                    if (val==andValues[k-1] && dp[j][k-1]<Infinity)
                        dp[i][k]=Math.min(dp[i][k],dp[j][k-1]+nums[i-1]);
                }
            }
        }
        return dp[n][m]==Infinity?-1:dp[n][m];
    }
}

Complexity

  • ⏰ Time complexity: O(m * n^2) — For each subarray, try all possible previous splits.
  • 🧺 Space complexity: O(m * n) — For DP table.