We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Sum of Values by Dividing Array

Number: 3364

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an array nums and a target array andValues, divide nums into m disjoint contiguous subarrays such that for the iᵗʰ subarray the bitwise AND of its elements equals andValues[i]. The value of a subarray is its last element, and the goal is to minimize the sum of these values. If it is impossible to partition nums accordingly, return -1.

Key Insights

  • We must partition the nums array into exactly m contiguous segments.
  • For each segment, the bitwise AND of elements must equal the given andValues element.
  • The objective is to minimize the sum of the last elements of each segment.
  • Since m ≤ 10 but n can be as high as 10⁴, dynamic programming over partition positions is a natural choice.
  • The bitwise AND operation is monotonic in the sense that adding more numbers can only turn 1s off.
  • As we consider segments ending at a given index, we update the cumulative AND backwards and check if it equals the required target.

Space and Time Complexity

Time Complexity: O(n² * m) in the worst-case due to checking all possible segment breaks and calculating the cumulative AND.
Space Complexity: O(n * m) for the DP table.

Solution

We solve the problem using dynamic programming.
Define dp[i][j] as the minimum possible sum when partitioning the first i elements of nums into j segments satisfying the AND condition.
For every potential endpoint i, and for every segment count seg from 1 to m, we iterate backwards to try every possible start for the current segment. During the backward traversal, we maintain a running bitwise AND of the segment. If at any point this running AND equals andValues[seg-1] (the target for the current segment), we update dp[i][seg] with dp[k][seg-1] + nums[i-1] (using the last element of the current segment as its value).
Finally, if dp[n][m] is still infinity (an unattainable value), then no valid partition exists and we return -1. Otherwise, dp[n][m] gives the minimum sum.

Code Solutions

# Python implementation with line-by-line comments

def minSumOfValues(nums, andValues):
    n = len(nums)
    m = len(andValues)
    INF = float('inf')
    
    # dp[i][j] represents the minimum sum for the first i numbers divided into j segments.
    dp = [[INF] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = 0  # Base case: zero elements partitioned into zero segments cost 0
    
    # Iterate over positions in the nums array
    for i in range(1, n + 1):
        # Try each possible number of segments from 1 up to min(m, i)
        for seg in range(1, min(m, i) + 1):
            current_and = None
            # Explore possible starting positions for current segment by iterating backwards
            for k in range(i - 1, seg - 2, -1):
                if current_and is None:
                    current_and = nums[k]
                else:
                    current_and &= nums[k]
                # If the current segment's AND equals the target andValues for this segment
                if current_and == andValues[seg - 1]:
                    if dp[k][seg - 1] != INF:
                        dp[i][seg] = min(dp[i][seg], dp[k][seg - 1] + nums[i - 1])
    
    return dp[n][m] if dp[n][m] != INF else -1

# Example usage:
print(minSumOfValues([1,4,3,3,2], [0,3,3,2]))  # Expected output: 12
← Back to All Questions