3117. Minimum Sum of Values by Dividing Array

Description

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

 

Solutions

Solution: Dynamic Programming + Bit Manipulation

• Time complexity: O(mn*log(Max(nums)))
• Space complexity: O(mn*log(Max(nums)))

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number[]} andValues
 * @return {number}
 */
const minimumValueSum = function (nums, andValues) {
  const n = nums.length;
  const m = andValues.length;
  const maxNum = Math.max(...nums);
  const log = 32 - Math.clz32(maxNum);
  const MAX_MASK = (1 << log) - 1;
  const dp = Array.from({ length: n }, () => {
    return new Array(m)
      .fill('')
      .map(() => new Map());
  });

  const getMinSumValues = (i, j, mask) => {
    if (i >= n && j >= m) return 0;

    if (i >= n || j >= m) return Number.MAX_SAFE_INTEGER;

    if (dp[i][j].has(mask)) return dp[i][j].get(mask);

    const num = nums[i];
    const nextMask = mask & num;
    const target = andValues[j];

    if (nextMask < target) return Number.MAX_SAFE_INTEGER;

    let result = getMinSumValues(i + 1, j, nextMask);

    if (nextMask === target) {
      const sum = num + getMinSumValues(i + 1, j + 1, MAX_MASK);

      result = Math.min(sum, result);
    }

    dp[i][j].set(mask, result);

    return result;
  };

  const sum = getMinSumValues(0, 0, MAX_MASK);

  return sum === Number.MAX_SAFE_INTEGER ? -1 : sum;
};