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

Number: 3654

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums and integers k, op1, and op2, you may perform two types of operations – each at most once per index – with overall limits op1 for Operation 1 and op2 for Operation 2. Operation 1 divides a chosen element by 2 (rounding up), and Operation 2 subtracts k from the element (only if the element is at least k). Both operations can be applied to the same index (each at most once). The goal is to choose operations (or none) for each element such that the sum of the resulting array is minimized.

Key Insights

  • For each array element, there are up to four choices:
    • Do nothing.
    • Use Operation 1 only.
    • Use Operation 2 only (if the element is at least k).
    • Use both operations (in two orders; note that the order matters because of operation preconditions).
  • When using both operations:
    • Option “op1 then op2” is valid only if after halving (rounded up) the value is still at least k.
    • Option “op2 then op1” only requires that the original value is at least k.
  • Precompute for each element the result after each possible operation combination along with the cost in terms of op1 and op2 that would be used.
  • Apply a dynamic programming (DP) solution that iterates over the array and for each element considers all valid choices, “packing” the limited number of op1 and op2 operations.
  • The DP state is defined as dp[i][j][l] representing the minimum sum achievable after processing some elements while having used j instances of Operation 1 and l instances of Operation 2. (In an actual implementation the DP can be optimized to 2D by iterating index by index.)

Space and Time Complexity

Time Complexity: O(n * op1 * op2 * 4) ≈ O(n * op1 * op2) where n <= 100 and op1, op2 <= 100. Space Complexity: O(op1 * op2) for the DP table.

Solution

The solution uses a dynamic programming approach. For each element, we consider all possible operations:

  1. No-op with cost = a[i] and no operations used.
  2. Operation 1 only: new value = ceil(a[i] / 2) and uses 1 Operation 1.
  3. Operation 2 only (if a[i] >= k): new value = a[i] - k and uses 1 Operation 2.
  4. Both operations: Two possible orders:
    • op1 then op2, which requires ceil(a[i]/2) >= k and yields new value = ceil(a[i]/2) - k.
    • op2 then op1, which always is valid if a[i] >= k, yielding new value = ceil((a[i]-k)/2). We take the minimum of these two outcomes if both are valid. For each element, we try to “pack” one of these choices into our DP. The DP state tracks the number of used op1 and op2 operations (since each operation can only be used overall up to op1 and op2 times, respectively). At the end, we take the minimum sum obtained.

We use a 2D DP array updated for each element where the indices represent the count of operations used so far. For each element and for every valid state, we update the new state with the cost of picking one of the 4 options if it does not exceed op1 or op2 limits.

Code Solutions

# Python solution with line-by-line comments
import math

def minimumArraySum(nums, k, op1, op2):
    n = len(nums)
    # Initialize dp table with dimensions (op1+1) x (op2+1)
    # dp[x][y] is the minimum sum achievable using x operations of type1 and y of type2 so far.
    dp = [[float('inf')] * (op2+1) for _ in range(op1+1)]
    dp[0][0] = 0

    # Process each element in nums
    for a in nums:
        # For current element, precompute all possible options
        # Each option is tuple: (new_value, op1_used, op2_used)
        options = []
        # Option 0: no operation
        options.append((a, 0, 0))
        
        # Option 1: Operation 1 only (divide by 2 rounding up)
        op1_only = math.ceil(a / 2)
        options.append((op1_only, 1, 0))
        
        # Option 2: Operation 2 only (subtract k), valid if a >= k
        if a >= k:
            op2_only = a - k
            options.append((op2_only, 0, 1))
        
        # Option 3: Both operations (if a >= k)
        if a >= k:
            # Order: op2 then op1: always valid.
            both_order_b = math.ceil((a - k) / 2)
            both_val = both_order_b
            # Order: op1 then op2: valid only if after op1, the number is >= k.
            op1_then = math.ceil(a / 2)
            if op1_then >= k:
                both_order_a = op1_then - k
                both_val = min(both_val, both_order_a)
            options.append((both_val, 1, 1))
        
        # Update dp table for current element.
        new_dp = [[float('inf')] * (op2+1) for _ in range(op1+1)]
        # Iterate over the possible dp states so far.
        for used1 in range(op1+1):
            for used2 in range(op2+1):
                if dp[used1][used2] == float('inf'):
                    continue
                # Try all possible options for this element.
                for cost, use1, use2 in options:
                    new_used1 = used1 + use1
                    new_used2 = used2 + use2
                    # Only update if we don't exceed available operations.
                    if new_used1 <= op1 and new_used2 <= op2:
                        new_dp[new_used1][new_used2] = min(new_dp[new_used1][new_used2], dp[used1][used2] + cost)
        dp = new_dp

    # The answer is the minimum sum achieved across all valid dp states.
    ans = float('inf')
    for used1 in range(op1+1):
        for used2 in range(op2+1):
            ans = min(ans, dp[used1][used2])
    return ans

# Example test cases
print(minimumArraySum([2,8,3,19,3], 3, 1, 1))  # Expected output: 23
print(minimumArraySum([2,4,3], 3, 2, 1))        # Expected output: 3
← Back to All Questions