Skip to content

3117. Minimum Sum of Values by Dividing Array 👍

  • Time: $O(n \cdot 10 \cdot \log\max(\texttt{nums}))$
  • Space: $O(n \cdot 10 \cdot \log\max(\texttt{nums}))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
    vector<vector<unordered_map<int, int>>> mem(
        nums.size(), vector<unordered_map<int, int>>(andValues.size()));
    const int ans = minimumValueSum(nums, andValues, 0, 0, kFullMask, mem);
    return ans == kInf ? -1 : ans;
  }

 private:
  static constexpr int kInf = 1'000'000'000;
  static constexpr int kFullMask = (1 << 17) - 1;

  // Returns the minimum value sum of nums[i..n) and andValues[j..m), where
  // `mask` is the running value of the current subarray.
  int minimumValueSum(const vector<int>& nums, const vector<int>& andValues,
                      int i, int j, int mask,
                      vector<vector<unordered_map<int, int>>>& mem) {
    if (i == nums.size() && j == andValues.size())
      return 0;
    if (i == nums.size() || j == andValues.size())
      return kInf;
    if (const auto it = mem[i][j].find(mask); it != mem[i][j].cend())
      return it->second;
    mask &= nums[i];
    if (mask < andValues[j])
      return mem[i][j][mask] = kInf;
    if (mask == andValues[j])
      // 1. Keep going.
      // 2. End the subarray here and pick nums[i], then fresh start.
      return mem[i][j][mask] =
                 min(minimumValueSum(nums, andValues, i + 1, j, mask, mem),
                     nums[i] + minimumValueSum(nums, andValues, i + 1, j + 1,
                                               kFullMask, mem));
    // Keep going.
    return mem[i][j][mask] =
               minimumValueSum(nums, andValues, i + 1, j, mask, mem);
  };
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
  public int minimumValueSum(int[] nums, int[] andValues) {
    Map<Integer, Integer>[][] mem = new Map[nums.length][andValues.length];
    Arrays.stream(mem).forEach(A -> Arrays.setAll(A, j -> new HashMap<>()));
    final int ans = minimumValueSum(nums, andValues, 0, 0, FULL_MASK, mem);
    return ans == INF ? -1 : ans;
  }

  private static final int INF = 1_000_000_000;
  private static final int FULL_MASK = (1 << 17) - 1;

  // Returns the minimum value sum of nums[i..n) and andValues[j..m), where
  // `mask` is the running value of the current subarray.
  private int minimumValueSum(int[] nums, int[] andValues, int i, int j, int mask,
                              Map<Integer, Integer>[][] mem) {
    if (i == nums.length && j == andValues.length)
      return 0;
    if (i == nums.length || j == andValues.length)
      return INF;
    if (mem[i][j].containsKey(mask))
      return mem[i][j].get(mask);
    mask &= nums[i];
    if (mask < andValues[j]) {
      mem[i][j].put(mask, INF);
      return INF;
    }
    if (mask == andValues[j]) {
      // 1. Keep going.
      // 2. End the subarray here and pick nums[i], then fresh start.
      final int res =
          Math.min(minimumValueSum(nums, andValues, i + 1, j, mask, mem),
                   nums[i] + minimumValueSum(nums, andValues, i + 1, j + 1, FULL_MASK, mem));
      mem[i][j].put(mask, res);
      return res;
    }
    // Keep going.
    final int res = minimumValueSum(nums, andValues, i + 1, j, mask, mem);
    mem[i][j].put(mask, res);
    return res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def minimumValueSum(self, nums: list[int], andValues: list[int]) -> int:
    n = len(nums)
    m = len(andValues)

    @functools.lru_cache(None)
    def dp(i: int, j: int, mask: int) -> int:
      """
      Returns the minimum value sum of nums[i..n) and andValues[j..m), where
      `mask` is the running value of the current subarray.
      """
      if i == n and j == m:
        return 0
      if i == n or j == m:
        return math.inf
      mask &= nums[i]
      if mask < andValues[j]:
        return math.inf
      if mask == andValues[j]:
        # 1. Keep going.
        # 2. End the subarray here and pick nums[i], then fresh start.
        return min(dp(i + 1, j, mask),
                   nums[i] + dp(i + 1, j + 1, -1))
      return dp(i + 1, j, mask)  # Keep going.

    ans = dp(0, 0, -1)
    return ans if ans < math.inf else -1