3117. Minimum Sum of Values by Dividing Array LeetCode Solution
In this guide, you will get 3117. Minimum Sum of Values by Dividing Array LeetCode Solution with the best time and space complexity. The solution to Minimum Sum of Values by Dividing Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Sum of Values by Dividing Array
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,4] as 1 & 4 == 0.
[3] as the bitwise AND of a single element subarray is that element itself.
[3] as the bitwise AND of a single element subarray is that element itself.
[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:
[[2,3,5],[7,7,7],[5]] with the sum of the values 5 + 7 + 5 == 17.
[[2,3,5,7],[7,7],[5]] with the sum of the values 7 + 7 + 5 == 19.
[[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.
Time Complexity: O(n \cdot 10 \cdot \log\max(\texttt{nums}))
Space Complexity: O(n \cdot 10 \cdot \log\max(\texttt{nums}))
3117. Minimum Sum of Values by Dividing Array LeetCode Solution in C++
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);
};
}; /* code provided by PROGIEZ */
3117. Minimum Sum of Values by Dividing Array LeetCode Solution in Java
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, kFullMask, mem);
return ans == kInf ? -1 : ans;
}
private static final int kInf = 1_000_000_000;
private static final 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.
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 kInf;
if (mem[i][j].containsKey(mask))
return mem[i][j].get(mask);
mask &= nums[i];
if (mask < andValues[j]) {
mem[i][j].put(mask, kInf);
return kInf;
}
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, kFullMask, 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;
}
} // code provided by PROGIEZ
3117. Minimum Sum of Values by Dividing Array LeetCode Solution in Python
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 # code by PROGIEZ
