Facebook Pixel

3117. Minimum Sum of Values by Dividing Array

HardBit ManipulationSegment TreeQueueArrayBinary SearchDynamic Programming
Leetcode Link

Problem Description

You have two arrays, nums and andValues, with lengths n and m respectively. The goal is to partition the nums array into m disjoint contiguous subarrays. For each of these subarrays defined by [l_i, r_i], the bitwise AND of elements must equal andValues[i]. Formally, for subarray [l_i, r_i], the condition is nums[l_i] & nums[l_i + 1] & ... & nums[r_i] == andValues[i], for every 1 <= i <= m. The definition of a subarray value is its last element. The task is to find the minimum possible sum of these subarray values. If it's impossible to partition nums in the required manner, return -1.

Intuition

To solve this problem, we can utilize a recursive approach with memoization. The main idea is to define a function dfs(i, j, a) representing the minimum sum of subarray values starting from the i-th element, divided into j subarrays, with a as the current subarray's bitwise AND result in progress.

The execution involves:

  1. Edge Case Check: If the remaining elements n - i are less than the needed subarrays m - j, return infinity (inf), indicating it's impossible to achieve the required configuration.
  2. Subarray Completion Check: If we’ve divided j subarrays and j = m, check if all elements in nums are used (i = n). If so, return 0 (indicating a valid partition), otherwise return inf.
  3. Bitwise AND Update: Update the current subarray's bitwise AND with nums[i]. If this new AND is less than the required andValues[j], it's invalid, return inf.
  4. Decision Making: We have two choices:
    • Continue the current subarray without dividing: Corresponds to dfs(i + 1, j, a).
    • Divide here and start a new subarray: Hence compute dfs(i + 1, j + 1, -1) + nums[i], meaning we end this subarray and include nums[i] as its last value.
  5. Result Storage: Use memoization to store results of each state to avoid recomputation.

The initial call dfs(0, 0, -1) starts from the beginning of the array with no subarrays formed yet and using -1 as a neutral AND value. If the result is finite, it represents the minimum possible sum; otherwise, return -1.

Learn more about Segment Tree, Queue, Binary Search and Dynamic Programming patterns.

Solution Approach

The solution utilizes a recursive algorithm with memoization. Here's the detailed breakdown of the approach:

  1. Recursive Function Definition: We define dfs(i, j, a):

    • i represents the starting index in nums for our current consideration.
    • j denotes the number of subarrays we have already divided.
    • a denotes the current AND result of the elements in the subarray being formed.

  2. Base Case and Edge Handling:

    • If the remaining elements (n - i) are fewer than the subarrays needed (m - j), return an impossibly large value (inf), since it's crucial to form exactly m subarrays.
    • If j equals m, check if i is also at n. If true, all required subarrays are formed and return 0 to signify a valid partitioning. Otherwise, return inf to indicate an invalid partition.

  3. Bitwise AND Update:

    • Update a with the bitwise AND operation with nums[i].
    • If a is less than andValues[j], return inf as the condition for the j-th subarray cannot be met.

  4. Recursive Decision Making:

    • Two pathways are considered:
      • Continue the Current Subarray: Call dfs(i + 1, j, a) meaning extend the current subarray to include nums[i].
      • End and Start New Subarray: If a meets andValues[j], consider dividing, meaning this subarray is viable and ends here. Add the last element's value (nums[i]) to the subarray sum: dfs(i + 1, j + 1, -1) + nums[i].

  5. Memoization:

    • Utilize Python's @cache decorator to memoize results, ensuring that previously computed states do not have to be recalculated, enhancing efficiency.

  6. Initialization and Result:

    • Begin recursion with dfs(0, 0, -1) to go through the entire array starting fresh with the parameters.
    • Evaluate the result; if it's less than infinity, it's the minimal subarray value sum. Otherwise, return -1 to signify an invalid partition is impossible.

The code structure is neat, employing recursion for exploration and memoization to optimize overlapping subproblems.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple example with nums = [3, 5, 8, 2] and andValues = [3, 2].

Objective: Partition nums into 2 contiguous subarrays such that:

  • The first subarray's AND equals 3
  • The second subarray's AND equals 2
  • The goal is to minimize the sum of the last elements in these subarrays.

Here's the step-by-step process:

  1. Recursive Function Initialization: Start with dfs(0, 0, -1):

    • i = 0: Start index at the beginning of nums.
    • j = 0: No subarrays divided yet.
    • a = -1: Neutral AND value starting fresh.

  2. First Recursive Decision:

    • At i = 0, nums[0] = 3, update a = -1 & 3 = 3.
    • Check validity: a (3) >= andValues[0] (3), the condition is satisfied.

  3. Explore Options:

    • Extend Current Subarray: Call dfs(1, 0, 3) to include nums[1].
    • Start New Subarray: Since the current AND condition is met, call dfs(1, 1, -1) after concluding the current subarray at nums[0], add its value to the sum.

  4. Continue Exploration at i = 1:

    • Extending from dfs(1, 0, 3):
      • a = 3 & 5 = 1, this doesn't satisfy andValues[0], hence return inf.
    • New subarray from dfs(1, 1, -1):
      • a = -1 & 5 = 5, doesn't meet andValues[1], more elements needed.

  5. Proceed to i = 2:

    • At i = 1, continuing from dfs(1, 1, 5), extend to dfs(2, 1, 5):
      • a = 5 & 8 = 0, doesn’t meet andValues[1].

  6. Next Subarray at i = 2 Starting New:

    • Call dfs(2, 2, -1) after closing previous at nums[1], add nums[1] to possible sum (only if 5 == 2).

  7. Arrival at Last Index i = 3:

    • From dfs(2, 1, 5), reach dfs(3, 1, 0):
      • Extend or not; here decisions will branch into completing further if valid.

  8. Check Valid Subarray Formulation:

    • Those yields no valid bitwise AND equals giving 2 on extending and require backtracking.

  9. Achieving Solution:

    • By tracing valid paths ending subarrays as required:
      • Optimal usually involves [3, 5] ending with 8: check each combination.

  10. Result:

    • Analyze returns; compute the minimum concludes:
      • In our exploration, valid 5 + 8 = 13.

If no configuration works, the result will be -1. For this example, we achieve a minimal sum of valid subarray endings.

Solution Implementation

1from typing import List
2from functools import cache
3import math
4
5class Solution:
6    def minimumValueSum(self, nums: List[int], andValues: List[int]) -> int:
7        # Define a recursive function with memoization to solve the subproblems
8        @cache
9        def dfs(i: int, j: int, accumulated_and: int) -> int:
10            # If remaining nums are less than remaining andValues to satisfy, return infinity
11            if n - i < m - j:
12                return math.inf
13          
14            # If we have satisfied all 'andValues', check if we've also used all 'nums'
15            if j == m:
16                return 0 if i == n else math.inf
17          
18            # Update the accumulated AND value
19            accumulated_and &= nums[i]
20          
21            # If the accumulated AND value is less than required, return infinity
22            if accumulated_and < andValues[j]:
23                return math.inf
24          
25            # Option 1: Skip the current number in 'nums'
26            result = dfs(i + 1, j, accumulated_and)
27          
28            # Option 2: Use the current number if AND condition is met
29            if accumulated_and == andValues[j]:
30                result = min(result, dfs(i + 1, j + 1, -1) + nums[i])
31
32            return result
33
34        # Initialize problem size
35        n, m = len(nums), len(andValues)
36      
37        # Start the dfs from the first index with an initial AND value of -1 (all bits set)
38        result = dfs(0, 0, -1)
39      
40        # Return the result if it's valid, otherwise return -1
41        return result if result < math.inf else -1
42
1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    private int[] nums;
6    private int[] andValues;
7    private final int INF = 1 << 29;  // A large constant to represent infinity
8    private Map<Long, Integer> memoizationMap = new HashMap<>();
9
10    public int minimumValueSum(int[] nums, int[] andValues) {
11        this.nums = nums;  // Array of numbers
12        this.andValues = andValues;  // Array of AND values
13        int result = dfs(0, 0, -1);  // Start the recursive DFS function
14        return result >= INF ? -1 : result;  // If the result is infinite, return -1
15    }
16
17    private int dfs(int numsIndex, int andValuesIndex, int accumulatedAnd) {
18        // If there aren't enough numbers left to satisfy remaining AND values, return infinity
19        if (nums.length - numsIndex < andValues.length - andValuesIndex) {
20            return INF;
21        }
22        // If all AND values are satisfied, check if all numbers have been used
23        if (andValuesIndex == andValues.length) {
24            return numsIndex == nums.length ? 0 : INF;
25        }
26      
27        accumulatedAnd &= nums[numsIndex];  // Update accumulated AND value
28        // If accumulated AND can't satisfy the current AND value, return infinity
29        if (accumulatedAnd < andValues[andValuesIndex]) {
30            return INF;
31        }
32
33        // Create a unique key using numsIndex, andValuesIndex, and accumulatedAnd
34        long key = ((long) numsIndex << 36) | ((long) andValuesIndex << 32) | accumulatedAnd;
35        // Use the memoization hash map to check if this state has been computed
36        if (memoizationMap.containsKey(key)) {
37            return memoizationMap.get(key);
38        }
39
40        // Explore not taking the current number, move to the next index in nums
41        int minCost = dfs(numsIndex + 1, andValuesIndex, accumulatedAnd);
42
43        // Explore taking the current number if the accumulated AND matches the current andValues entry
44        if (accumulatedAnd == andValues[andValuesIndex]) {
45            minCost = Math.min(minCost, dfs(numsIndex + 1, andValuesIndex + 1, -1) + nums[numsIndex]);
46        }
47      
48        // Memorize the computed result for the current state
49        memoizationMap.put(key, minCost);
50        return minCost;
51    }
52}
53
1// A C++ class solution for calculating the minimum sum needed 
2// to reach a specific set of 'AND' values using dynamic programming and memoization.
3class Solution {
4public:
5    // The main function that initializes the necessary variables 
6    // and calls the recursive DFS function.
7    int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
8        this->nums = nums;
9        this->andValues = andValues;
10        n = nums.size();
11        m = andValues.size();
12      
13        // Initiate recursive Depth-First Search (DFS) from the first elements
14        int result = dfs(0, 0, -1);
15      
16        // If the result is inf (a large number), return -1, indicating no solution
17        return result >= inf ? -1 : result;
18    }
19
20private:
21    // Member variables
22    vector<int> nums;      // The main number array
23    vector<int> andValues; // The target "AND" values
24    int n;                 // Size of nums
25    int m;                 // Size of andValues
26    const int inf = 1 << 29;  // A large constant value to represent infinity
27    unordered_map<long long, int> memoization; // Cache for memoization
28
29    // Recursive DFS function to calculate the minimum value sum.
30    int dfs(int i, int j, int a) {
31        // If remaining nums are less than andValues needed, return inf
32        if (n - i < m - j) {
33            return inf;
34        }
35        // If all target andValues are matched, check the position in nums 
36        if (j == m) {
37            return i == n ? 0 : inf;
38        }
39        // Calculate the AND on the current number
40        a &= nums[i];
41
42        // If the AND operation does not meet the required andValue[j], return inf
43        if (a < andValues[j]) {
44            return inf;
45        }
46
47        // Create a unique key for memoization
48        long long key = (static_cast<long long>(i) << 36) | (static_cast<long long>(j) << 32) | a;
49
50        // Use memoization to check previously computed answers
51        if (memoization.contains(key)) {
52            return memoization[key];
53        }
54
55        // Option 1: Skip the current number
56        int result = dfs(i + 1, j, a);
57
58        // Option 2: If the AND matches the required value, include the current number
59        if (a == andValues[j]) {
60            result = min(result, dfs(i + 1, j + 1, -1) + nums[i]);
61        }
62
63        // Store the result in the memoization table and return
64        return memoization[key] = result;
65    }
66};
67
1// Define a function that calculates the minimum value sum based on two input arrays: nums and andValues
2function minimumValueSum(nums: number[], andValues: number[]): number {
3
4    // Extract the lengths of the input arrays
5    const [n, m] = [nums.length, andValues.length];
6
7    // Create a map to memoize the results of sub-problems for dynamic programming
8    const f: Map<bigint, number> = new Map();
9
10    // Define a helper function that uses Depth-First Search (DFS) with memorization
11    const dfs = (i: number, j: number, a: number): number => {
12
13        // If remaining elements in nums are fewer than needed to complete andValues, return Infinity
14        if (n - i < m - j) {
15            return Infinity;
16        }
17
18        // If the andValues array has been fully matched, check if all nums have been used, else return Infinity
19        if (j === m) {
20            return i === n ? 0 : Infinity;
21        }
22
23        // Update the accumulated 'and' value with the current element in nums
24        a &= nums[i];
25
26        // If the current accumulated 'and' value is less than the target value, return Infinity
27        if (a < andValues[j]) {
28            return Infinity;
29        }
30
31        // Create a unique key for storing the current state (combination of index and 'and' value) in the map
32        const key = (BigInt(i) << 36n) | (BigInt(j) << 32n) | BigInt(a);
33      
34        // If this state has been computed previously, return the stored result
35        if (f.has(key)) {
36            return f.get(key)!;
37        }
38
39        // Compute the minimal sum without selecting the current element
40        let ans = dfs(i + 1, j, a);
41
42        // If the current accumulated 'and' value matches the target, consider selecting the element
43        if (a === andValues[j]) {
44            // Compute the minimal sum by selecting the current element and moving to the next target in andValues
45            ans = Math.min(ans, dfs(i + 1, j + 1, -1) + nums[i]);
46        }
47
48        // Store the result in the map
49        f.set(key, ans);
50
51        // Return the computed minimum sum
52        return ans;
53    };
54
55    // Start the DFS and calculate the minimum value sum
56    const ans = dfs(0, 0, -1);
57
58    // If the result is Infinity (no solution found), return -1, otherwise return the calculated sum
59    return ans >= Infinity ? -1 : ans;
60}
61

Time and Space Complexity

The time complexity of the code is O(n \times m \times \log M). This arises from the recursive depth of the dfs function, which can potentially go as deep as n calls, with each call potentially spawning another set of recursive calls of order up to m, and during each call, bitwise operations depend logarithmically on the size of the integer in terms of M.

The space complexity is O(n \times m \times \log M). This is due to the memoization storage required by the @cache decorator, which needs to store results for each unique combination of the state (i, j, a), leading to memory usage that scales with the depth and breadth of the recursive state space.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

In a binary min heap, the minimum element can be found in:

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

Queue Intro

Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More